int euler_phi(int n) { int ans=n; int m=sqrt(n+0.5); for(int i=2;i<=m;i++) if(n % i == 0){ ans=ans/i*(i-1); while( n % i == 0) n/=i; } if(n>1) ans=ans/n*(n-1); //针对n为质数的情况 return ans; }
int phi[MAXN]; void phi_table(int n) { for(int i=2;i<=n;i++) phi[i]=0; phi[1]=1; for(int i=2;i<=n;i++) if(!phi[i]) for(int j=i;j<=n;j+=i){ if(!phi[j]) phi[j]=j; phi[j]=phi[j]/i*(i-1); } }
线性筛选求莫比乌斯反演函数代码。
void Init() { memset(vis,0,sizeof(vis)); mu[1] = 1; cnt = 0; for(int i=2; i<N; i++) { if(!vis[i]) { prime[cnt++] = i; mu[i] = -1; } for(int j=0; j<cnt&&i*prime[j]<N; j++) { vis[i*prime[j]] = 1; if(i%prime[j]) mu[i*prime[j]] = -mu[i]; else { mu[i*prime[j]] = 0; break; } } } }