题目看这里
一个简单的反演题目:

∑i=1n∑j=1nϕ(gcd(ϕ(i),ϕ(j)))∑i=1n∑j=1nϕ(gcd(ϕ(i),ϕ(j)))

首先做一下变换
∑ni=1∑nj=1ϕ(gcd(ϕ(i),ϕ(j)))∑i=1n∑j=1nϕ(gcd(ϕ(i),ϕ(j)))
=∑nd=1ϕ(d)∗f(d)=∑d=1nϕ(d)∗f(d)
这里f(d)=∑i,j[gcd(ϕ(i),ϕ(j))=d]f(d)=∑i,j[gcd(ϕ(i),ϕ(j))=d]
表示有多少对i,j满足它们的ϕϕ值的最大公约数为d
我们令F(d)=∑i,j[d|gcd(ϕ(i),ϕ(j))]F(d)=∑i,j[d|gcd(ϕ(i),ϕ(j))],就有F(n)=∑n|df(d)F(n)=∑n|df(d)
反演得到f(n)=∑dF(n∗d)∗μ(d)f(n)=∑dF(n∗d)∗μ(d)
所以原式可以写成∑i∗j<=nϕ(i)∗F(i∗j)∗μ(j)∑i∗j<=nϕ(i)∗F(i∗j)∗μ(j)
预处理μ,ϕμ,ϕ和FF的值就可以了




#pragma GCC optimize("O3")#pragma GCC optimize("O3")



#pragma G++ optimize("O3")#pragma G++ optimize("O3")



#include<stdio.h>#include<stdio.h>



#include<string.h>#include<string.h>



#include<algorithm>#include<algorithm>



#define N 2000010 #define N 2000010 



#define LL long long#define LL long long



using namespace std;using namespace std;



int n,T; long long S;int n,T; long long S;



int w[N>>2],t,phi[N],mu[N],vis[N],c[N];int w[N>>2],t,phi[N],mu[N],vis[N],c[N];



inline LL F(int x){  return (LL)c[x]∗c[x]; }inline LL F(int x){ return (LL)c[x]∗c[x]; }



inline void cal(){ inline void cal(){



scanf("%d",&n); memset(c,S=0,sizeof c);scanf("%d",&n); memset(c,S=0,sizeof c);



for(int i=1;i<=n;++i) ++c[phi[i]];for(int i=1;i<=n;++i) ++c[phi[i]];



for(int i=1;i<=n;++i)for(int i=1;i<=n;++i)



for(int j=i+i;j<=n;j+=i) c[i]+=c[j];for(int j=i+i;j<=n;j+=i) c[i]+=c[j];



for(int i=1;i<=n;++i) if(mu[i])for(int i=1;i<=n;++i) if(mu[i])



for(int j=1;i∗j<=n;++j)for(int j=1;i∗j<=n;++j)



S+=(LL)F(i∗j)∗mu[i]∗phi[j];S+=(LL)F(i∗j)∗mu[i]∗phi[j];



printf("%lld",S);printf("%lld",S);



}}



int main(){ int main(){



phi[1]=mu[1]=1;phi[1]=mu[1]=1;



for(int i=2;i<=2000000;++i){ for(int i=2;i<=2000000;++i){



if(!vis[i]){  mu[w[++t]=i]=−1; phi[i]=i−1; }if(!vis[i]){ mu[w[++t]=i]=−1; phi[i]=i−1; }



for(int j=1,k;(k=i∗w[j])<=2000000;++j){ for(int j=1,k;(k=i∗w[j])<=2000000;++j){



vis[k]=1;vis[k]=1;



if(i%w[j]==0){  phi[k]=phi[i]∗w[j]; mu[k]=0; break; }if(i%w[j]==0){ phi[k]=phi[i]∗w[j]; mu[k]=0; break; }



phi[k]=phi[i]∗(w[j]−1); mu[k]=−mu[i];phi[k]=phi[i]∗(w[j]−1); mu[k]=−mu[i];



} } 



}}



for(scanf("%d",&T);T−−;cal());for(scanf("%d",&T);T−−;cal());



}}

转载于:https://www.cnblogs.com/Extended-Ash/p/9477078.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/95575945

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。