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;
}
推荐阅读
- 前沿论文|论文精读（Neural Architecture Search without Training）
- Book|Book Review: Foundations of Statistical Natural Language Processing
- 神经网络Neural|神经网络Neural Networks
- 关于蘑菇街算法数据流（ACM）实现方案
- 2021-03-19面部脂肪填充多久能消肿（ACMETEA是怎么提升成活率？都来看看！）
- ACM|HDU 5322 Hope (CDQ分治+NTT)
- acm基础|哈希has散列-字符串hash
- ACM OJ 2036 多边形面积计算
- ACM|回文树（自动机）（练习和总结）
- acm|扩展欧几里德算法(附证明)