锐客网

  1. 首页 > it技术 > >

Code|CodeForces 839 D.Winter is here（莫比乌斯反演+组合数学）

code莫比乌斯反演组合数学Forces

Description
给出 n 个正整数 a1,...,an ，从中选出 k 个数，若其 gcd 大于 1 ，则贡献为 k?gcd ，求贡献和
Input
第一行一整数 n ，之后输入 n 个正整数 ai(1≤n≤2?105,1≤ai≤106)
Output
输出贡献和，结果模 109+7
Sample Input
【Code|CodeForces 839 D.Winter is here（莫比乌斯反演+组合数学）】3
3 3 1
Sample Output
12
Solution
令 f(k,d) 表示选出 k 个数其 gcd 为 d 的方案数， F(k,d) 表示选出 k 个数其 gcd 被 d 整除的方案数，记 numd 表示 a1,a2,...,an 中可以被 d 整除的数的个数，则 F(k,d)=Cknumd
记 m=max(a1,a2,...,an) 为 d 可能取到的最大值
显然 F(k,d)=∑d|if(k,i) ，由莫比乌斯反演， f(k,d)=∑d|iμ(id)F(k,i)
枚举 k,d 得到贡献和 ans=∑k=1n∑d=2mk?f(k,d)=∑k=1n∑d=2m∑d|ik?μ(id)Cknumi=∑d=2m∑d|i∑k=1nk?Cknumi
而 ∑k=1nk?Cknumi=∑k=1numik?numi!k!?(numi?k)!=numi?∑k=1numiCk?1numi?1=numi?2numi?1:=g(i)
故 ans=∑i=2mg(i)(∑d|i,d>1μ(id))=∑i=2mg(i)(∑d|iμ(d)?μ(i))=∑i=2mg(i)?(φ(i)?μ(i))
Code

#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pairP; const int INF=0x3f3f3f3f,maxn=1000005; #define mod 1000000007 int phi[maxn],mu[maxn],p[maxn],f[maxn],n,num[maxn]; void init(int n=1e6) { int res=0; for(int i=2; i<=n; i++) { if(!phi[i])phi[i]=i-1,mu[i]=-1,p[res++]=i; for(int j=0; j=mod?x+y-mod:x+y; } int main() { init(); scanf("%d",&n); int m=0; for(int i=1; i<=n; i++) { int temp; scanf("%d",&temp); m=max(m,temp); num[temp]++; } for(int i=2; i<=m; i++) for(int j=2*i; j<=m; j+=i) num[i]+=num[j]; int ans=0; for(int i=2; i<=m; i++) if(num[i]) add(ans,(ll)(phi[i]-mu[i])*num[i]%mod*f[num[i]-1]%mod); printf("%d\n",ans); return 0; }

    推荐阅读


    上一篇：grpc- python调用c++的rpc服务

    下一篇：【小知识】关于package-lock.json的详细解释