学步园

题目链接·：http://acm.timus.ru/problem.aspx?space=1&num=1091

题目意思，让你在1 - s中找k个数的公因子大于1，问有多少种这样的组合。。。(1 <= k <= s <= 50)。

分析：

我们要找的k个的公因子大于1。而且k，s       小于50。

我们可以直接枚举大于1的素公因子。求出以该素因子为因子的数有多少个，然后组合就好。。

一开始，我就是这么单纯的认为是这样的。。仅仅是这样的。。。- - 。。

后来发现WA的已发不可收拾。。后来才知道，仅仅这样做的话肯定会多加了一部分。多加那部分呢？？

比如：k = 2 , s = 20。

2：2，4，6，8，10，12，14，16，18，20

3：3，6，9，12，15，18

5：5，10，15，20，

7：7，14

我们知道2：6，12，18

              3：6，12，18 这两种在组合的时候就会重复。

我们可以发现他们都是6的倍数。也就是说他们的公因子都为6 = 2 * 3。。去掉这一类的数就好。。。

容斥原理还需要更多的去理解。。。

Code：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

const int N = 20;
int f[N] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
int C(int n, int m)
{
    m = min(m, n - m);
    int ans = 1;
    for(int i = 1;  i <= m; i ++){
        ans = ans * (n - i + 1);
        ans = ans / i;
    }
    return ans;
}

int main()
{
    int k, s;
    while(cin >> k >> s){
        int ans = 0;
        for(int i = 0; i < 9; i ++){
            if(s / f[i] >= k)
            ans += C(s / f[i], k);
        }
        for(int i = 0; i < 9; i ++){
            for(int j = i + 1; j < 9; j ++)
            {
                if(s / (f[i] * f[j]) >= k){
                    ans -= C(s / (f[i] * f[j]), k);
                }
            }
        }
        if(ans <= 10000) cout << ans << endl;
        else cout << "10000" << endl;
    }
    return 0;
}

------>

Code(二进制写法)：)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

const int N = 20;
const int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int C(int n, int m)
{
    if(n < m) return 0;
    int ans = 1;
    m = min(m, n - m);
    for(int i = 1; i <= m; i ++){
        ans = ans * (n - i  + 1);
        ans = ans / i;
    }
    return ans ;
}

int solve(int k , int s)
{
    int ans = 0, top = 0;
    for(int i = 0; i < 10; i ++){
        if(s / prime[i] < k){
            top = i;
            break;
        }
    }
    for(int i = 1; i < (1 << top); i ++){
        int cnt = 0, tmp = 1;
        for(int j = 0; j < top; j ++){
            if(i & (1 << j)){
                tmp = tmp * prime[j];
                cnt ++;
            }
        }
        if(cnt % 2) ans += C(s / tmp, k);
        else ans -= C(s / tmp, k);
    }
    return ans;
}
int main()
{
//    freopen("1.txt", "r", stdin);
    int k, s;
    while(cin >> k >> s){
        int ans = solve(k, s);
        if(ans > 10000) ans = 10000;
        cout << ans << endl;
    }
    return 0;
}

容斥原理强大。。。学习了。。。 - -