URAL-1091-Tmutarakan Exams
将题意简化一下就是给你一个数s，要用1-s构造一个长度为序列保证n个数的最大公约数为1，且n个数均不相同。
我们直接构造不太好想，于是我们想如何构造出不满足情况的序列，那么就是最大公约数>=2.由于这道题s,k均<=50.所以我们可以枚举gcd为2-S，同样如果一个序列的gcd为4，那么他一定被gcd为2的计算过，所以我们还是只需要枚举所有质数的组合即可，当枚举gcd为2时，一共n个数，一共s/2种选择，那么C(s/2,n)即是最终答案，以此类推，容斥一下就解决了。
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 105;
long long c[maxn][maxn];
int pri[20]={
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,};
void getC()
{c[0][0]=1;for(int i=1;i<=100;i++){c[i][0]=c[i][i]=1;for(int j=0;j<i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1]);}
}
int main()
{int k,s;scanf("%d%d",&k,&s);getC();ll ans=0;for(int i=1;i<(1<<15);i++){ll num=1;int cnt=0;for(int j=0;j<15;j++){if(i&(1<<j)){cnt++;num*=pri[j];}}ll tmp=0;if(s/num>=k) tmp=c[s/num][k];if(cnt&1) ans+=tmp;else ans-=tmp;}printf("%lld\n",min(ans,(ll)10000));return 0;
}