(组合数学3.3.2.1)URAL 1091. Tmutarakan Exams(容斥定理)
/* * URAL_1091.cpp * * Created on: 2013年10月9日 * Author: Administrator */#include <iostream>#include <cstdio>using namespace std;int pp[52];int c[52][52];int k,s;void cal_prime(){pp[0]=pp[1]=1;int i,j;for(i = 2 ; i <= 50 ; ++i){if(pp[i]){continue;}for(j = i*2 ; j <= 50 ; j += i){pp[j] = 1;}}}void cal_number(){int i,j;for(i = 0 ; i <= 50 ; ++i){c[i][0] = 1;}for(i = 1 ; i <= 50 ; ++i){for(j = 1 ; j <= 50 ; ++j){c[i][j] = c[i-1][j] + c[i-1][j-1];}}}bool pxp(int a){int i;for(i = 2 ; i <= 50 ; ++i){if(!pp[i] && !pp[a/i] && i != a/i && (a % i == 0) ){return true;}}return false;}int work(){int i,j;int ans = 0;for(i = 2 ; i <= s ; i++){if(!pp[i]){int cnt = 0;for(j = i ; j <= s ; j +=i){cnt++;}ans += c[cnt][k];}else if(pxp(i)){int cnt = 0;for(j = i ; j <= s ; j +=i){cnt++;}ans -= c[cnt][k];}}return ans > 10000?10000:ans;}int main(){cal_prime();cal_number();scanf("%d%d",&k,&s);printf("%d\n",work());}