【URAL】1091 Tmutarakan Exams

题意：取k个不同的数，每个数不超过s，问种数。

若kx1,kx2,...,kx3满足条件，则x1,x2,...,x3必然满足条件。

因此枚举素数容斥，2*3*5*7>50，所以枚举之多三层。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 #define MAXN 60
 5 typedef long long LL;
 6 using namespace std;
 7 bool p[MAXN];
 8 vector<int> prime;
 9 LL C[MAXN][MAXN];
10 void Init() {
11     int i, j;
12     memset(p, true, sizeof(p));
13     for (i = 2; i < 10; i++) {
14         if (p[i]) {
15             for (j = i * i; j < MAXN; j += i)
16                 p[j] = false;
17         }
18     }
19     prime.clear();
20     for (i = 2; i < MAXN; i++) {
21         if (p[i])
22             prime.push_back(i);
23     }
24     memset(C, 0, sizeof(C));
25     for (i = 0; i < MAXN; i++)
26         C[i][0] = C[i][i] = 1;
27     for (i = 1; i < MAXN; i++) {
28         for (j = 1; j < i; j++)
29             C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
30     }
31 }
32 int main() {
33     LL ans;
34     int t, s, i, j, k;
35     Init();
36     while (~scanf("%d%d", &t, &s)) {
37         for (ans = i = 0; i < (int) prime.size(); i++)
38             ans += C[s / prime[i]][t];
39         for (i = 0; i < (int) prime.size(); i++) {
40             for (j = i + 1; j < (int) prime.size(); j++)
41                 ans -= C[s / prime[i] / prime[j]][t];
42         }
43         for (i = 0; i < (int) prime.size(); i++) {
44             for (j = i + 1; j < (int) prime.size(); j++) {
45                 for (k = j + 1; k < (int) prime.size(); k++)
46                     ans += C[s / prime[i] / prime[j]
47                             / prime[k]][t];
48             }
49         }
50         if (ans > 10000)
51             ans = 10000;
52         printf("%lld\n", ans);
53     }
54     return 0;
55 }