锐客网

  1. 首页 > it技术 > >

ACM_Ural|Ural 1091. Tmutarakan Exams (莫比乌斯反演)

题目链接： http://acm.timus.ru/problem.aspx?space=1&num=1091
【ACM_Ural|Ural 1091. Tmutarakan Exams (莫比乌斯反演)】题意：
从1~S个数字里选出K个数使得K个数的gcd > 1的选择情况数有多少种，注意的是，如果答案大于10000，输出10000即可。K<=S<=50
思路：
很简单的莫比乌斯反演水题，设F(x)为选出k个数的gcd为x的倍数的情况数，则反演函数f(x)即为选出k个数的gcd为x的情况数就可以了。
这题数据范围小，所以其实直接用容斥原理也可以做，莫比乌斯反演其实就是计算各个容斥系数。

#include typedef long long ll; const int maxn = 50 + 10; int mu[maxn], pnum, pri[maxn]; bool vis[maxn]; ll C[maxn][maxn]; // 莫比乌斯反演函数 void Mobius(int n) { mu[1] = 1; pnum = 0; vis[1] = 1; for(int i = 2; i <= n; i++) { if(!vis[i]) { pri[pnum++] = i; mu[i] = -1; } for(int j = 0; j < pnum; j++) { if(i * pri[j] > n)break; vis[i * pri[j]] = 1; if(i % pri[j] == 0) { mu[i * pri[j]] = 0; break; } mu[i * pri[j]] = -mu[i]; } } }void init(int n) { Mobius(n); C[0][0] = 1; for(int i = 1; i <= n; i++){ C[i][0] = 1; for(int j = 1; j <= n; j++) C[i][j] = C[i-1][j] + C[i-1][j-1]; } }int main() { init(50); int k, s; scanf("%d%d", &k, &s); ll ans = 0; for(int i = 1; i <= s; i++) { int cnt = s/i; ans += C[cnt][k]*mu[i]; } ans = C[s][k] - ans; // 计算出gcd=1的情况数，总情况减去gcd=1的情况数就是答案 if(ans >= 10000)ans = 10000; printf("%lld\n", ans); return 0; }



    推荐阅读


    上一篇：如何在SAS中直接使用Oracle特有函数--sas Pass-Through Facility

    下一篇：Kotlin 中的循环全解