​Problem - 803F - Codeforces​ [数论 容斥原理 + gcd]

张开发
• 2026/4/18 7:11:56 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

​Problem - 803F - Codeforces​ [数论 容斥原理 + gcd]
Problem - 803F - Codeforces题意很简单 求一共多少个子序列的gcd1显然 所有的子序列一共有2^n -1 个 我们可以考虑用全集减去所有的gcd1 的子序列我们用cnti 表示数组中i出现的次数 用sumi 表示数组中包含因子i的数字的个数 那么显然sumi 等于所有i的倍数的cnt的和 那么包含 因子i的子序列的个数就是2^(sumi)-1显然会有重复计算的部分 这个时候就要用到容斥原理 奇减偶加容斥原理的系数我们可以用莫比乌斯函数当数组大小是若干个不同的素数的时候 莫比乌斯函数为(-1^cnt 如果有一个素数出现多次 就是0 排除多余情况代码实现如下#include bits/stdc.h using namespace std; #define int long long const int N1e55,mod1e97; int a[N],cnt[N],sum[N]; int pow2[N]; vectorintminp,primes,mu; void sieve(int n){ minp.assign(n1,0); primes.clear(); mu.assign(n1,0); mu[1]1; for(int i2;in;i){ if(!minp[i]){ minp[i]i; primes.push_back(i); mu[i]-1; } for(auto p:primes){ if(i*pn)break; minp[i*p]p; if(pminp[i]){ break; } mu[i*p]-mu[i]; } } } void init(int n){ pow2[0]1;pow2[1]2; for(int i2;in;i){ pow2[i](pow2[i-1]pow2[i-1])%mod; } sieve(n); } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m0; cinn; for(int i1;in;i){ cina[i]; cnt[a[i]]; mmax(m,a[i]); } init(1e51); int anspow2[n]-1; for(int i2;im;i){ int sum0; for(int ji;jm;ji){ sum(1LL*sumcnt[j])%mod; } ans(ans1LL*mu[i]*(pow2[sum]-1)%modmod)%mod; } coutans\n; return 0; }

更多文章