原题： URAL 1091 http://acm.timus.ru/problem.aspx?space=1&num=1091
题意：要求找出K个不同的数字使他们有一个大于1的公约数，且所有的数字都不能大于一个指定的数字S。
解法：可以考虑每个S内的素数，此素数和它的所有倍数构成一个集合，则可以在这些集合中任意去k个元素，C(n,k)即为这种情况下的方法种数，比如K = 3，S = 10，
则可以形成3个集合： {2,4,6,8,10} , {3,6,9}, {5,10} ，第一个集合C(5,3)，第二个集合C(3,3)，第三个集合为0，同时可以看到，6在两个集合中出现了，所以要减去一个6的情况，这样就是容斥原理了。
枚举一个素数，两个素数即可，因为如果三个素数的话，公倍数至少为2x3x5 = 30， 此时S内是30的倍数只有一个（S<=50），就是30本身，此时要选K>=2个是不可能的。所以三个及以上可以不计。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
#define N 10007 ll C[][];
int prime[] = {,,,,,,,,}; void calc_C()
{
memset(C,,sizeof(C));
C[][] = C[][] = ;
for(int i=;i<=;i++)
{
C[i][] = ;
for(int j=;j<=;j++)
C[i][j] = C[i-][j] + C[i-][j-];
}
} int main()
{
int k,S,i,j,res,num,flag;
calc_C();
while(scanf("%d%d",&k,&S)!=EOF)
{
ll res = ;
flag = ;
for(i=;i<;i++)
{
num = S/prime[i];
if(num < k)
{
flag = i;
break;
}
else
res += C[num][k];
}
for(i=;i<flag;i++)
{
for(j=i+;j<flag;j++)
{
num = S/(prime[i]*prime[j]);
if(num < k)
break;
else
res -= C[num][k];
}
}
printf("%lld\n",min((ll),res));
}
return ;
}