什么是欧拉函数？
欧拉函数φ（x）为[1，x]中与x互质的数
几个重要结论
1.φ(1)=1 这个显而易见吧
2.φ(质数x)=x-1;
3.如果p|x,那么?(x∗p)=?(x)∗p,否则?(x∗p)=?(x)∗(p−1)。非常有用的结论
欧拉筛模板，时间复杂度O(n)，所以是线性筛
bool vis[maxn]; int prime[maxn]; int phi[maxn]; for(int i=2;i<=n;i++) { if(!vis[i]) { prime[++cnt]=i; phi[i]=i-1; } for(int j=1;j<=cnt&&prime[j]*i<=maxn;j++) { vis[prime[j]*i]=true; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } else phi[i*prime[j]]=phi[i]*(prime[j]-1); } }
原文：https://www.cnblogs.com/LJB666/p/10991711.html