Ural 1091. Tmutarakan Exams

1091. Tmutarakan Exams
Time Limit: 1.0 second
Memory Limit: 16 MB

University of New Tmutarakan trains the first-class specialists in mental arithmetic. To enter the University you should master arithmetic perfectly. One of the entrance exams at the Divisibility Department is the following. Examinees are asked to find K different numbers that have a common divisor greater than 1. All numbers in each set should not exceed a given number S. The numbers K and S are announced at the beginning of the exam. To exclude copying (the Department is the most prestigious in the town!) each set of numbers is credited only once (to the person who submitted it first).
Last year these numbers were K=25 and S=49 and, unfortunately, nobody passed the exam. Moreover, it was proved later by the best minds of the Department that there do not exist sets of numbers with the required properties. To avoid embarrassment this year, the dean asked for your help. You should find the number of sets of K different numbers, each of the numbers not exceeding S, which have a common divisor greater than 1. Of course, the number of such sets equals the maximal possible number of new students of the Department.
Input
The input contains numbers K and S (2 ≤ K ≤ S ≤ 50).
Output
You should output the maximal possible number of the Department's new students if this number does not exceed 10000 which is the maximal capacity of the Department, otherwise you should output 10000.
Sample
input output
3 10

11

题目大意： 对于k,s<=50，试统计{a1,a2,...,ak|ai<=s and gcd(a1,...ak)>1}的数目。

算法分析：首先按照约数分类{2，3，5，……，s}。

我们会注意到如下事实：如果gcd(x,y)!=1且x<y，那么按照约数x分类的集合A包含按照约数y分类的集合B。如：对s=20,x=2,y=4有：
A={2，4，6，8，10，12，14，16，18，20}
B={4，8，12，16，20}
再如s=20,x=3,y=6有：
A={3，6，9，12，15，18}
B={6,12,18}
显然均有：A包含B
所以由此事实知：我们只需要按照素数分类即可！
但问题又来了，这样分类计数仍有重复！如：
当p=2时，对应的集合为：A={2，4，6，8，10，12，14，16，18，20}
当p=3时，对应的集合为：B={3，6，9，12，15，18}
当k=2时，从A集合中取{6,12}时，从B集合中同时也可以取到{6，12},产生重复！！！咋办呢？？？
这时容斥原理可以派上用场！对于上面的那种情况只需要再减去按6分类的集合所产生的集合数。
由于s<=50,k>=2，所以只需要考虑这些素数{2,3,5,7,11,13,17,19,23}按这些素数进行分类
以及排除应的情况为6->(2,3),10->(2,5),14->(2,7),22->(2,11),15->(3,5),21->(3,7),其它的不需要考虑。
代码：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=60;
int c[maxn][maxn];//存储组合数C(n,m)
void getC()
{//C(n,m)=C(n-1,m)+C(n-1,m-1)
    for(int i=0;i<maxn;i++)
    {
        c[i][0]=1;
        c[i][1]=i;
        c[i][i]=1;
    }
    for(int i=1;i<maxn;i++)
    {
        for(int j=1;j<i;j++)
        {
            int sum=c[i-1][j]+c[i-1][j-1];
            if(sum>10000)   sum=10000;//对于10000的只需存储10000
            c[i][j]=sum;
        }
    }
}
int main()
{
    getC();
    int k,s;
    //while(scanf("%d%d",&k,&s)!=EOF){
    scanf("%d%d",&k,&s);
    int sum=0;
    int prime[9]={2,3,5,7,11,13,17,19,23};
    for(int i=0;i<9;i++)
    {
        if(s/prime[i]<k)    break;
        if(c[s/prime[i]][k]==10000)  {sum=100000;break;}
        sum+=c[s/prime[i]][k];
        //printf("c[%d][%d]=%d\n",s/prime[i],k,c[s/prime[i]][k]);
    }
    if(sum==100000)
    {
        printf("10000\n");
        //continue;
        return 0;
    }
    for(int i=1;i<=4;i++)
    {
        if(s/(prime[i]*2)<k)    break;
        sum-=c[s/(prime[i]*2)][k];
    }
    for(int i=2;i<=3;i++)
    {
        if(s/(prime[i]*3)<k)    break;
        sum-=c[s/(prime[i]*3)][k];
    }
    sum=min(sum,10000);
    printf("%d\n",sum);
    //}
    return 0;
}