什么是欧拉函数？

欧拉函数φ（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);    }}