定义

欧拉函数表示不大于的与互质的正整数的数量。特别的，。

性质

1.

若是质数，则。

2.

若，则

3.

若互质，则

代码

既然公式都有了，那代码就很好写了

cpp
int phi(int n){
    int res = n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0)(res/=i)*=(i-1);
        while(n%i==0)n/=i;
    }
    if(n>1)(res/=n)*(n-1);
}

复杂度

可以用筛法来求

cpp
int phi[MAXN];
void Init(int n){
    for(int i=1;i<=n;i++)phi[i]=i;
    for(int i=2;i<=n;i++)
        if(phi[i]==i)
            for(int j=i;j<=n;j+=i)phi[j]=phi[j]/i*(i-1);
}

复杂度

还可以优化

cpp
int phi[MAXN],np[MAXN],primes[MAXN],m;
void Init(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!np[i])primes[++m]=i,phi[i]=i-1;//性质一
        for(int j=1;j<=m;j++){
            int p = primes[j];
            if(p*i>n)break;
            np[p*i]=1;
            if(i%p==0)phi[p*i]=phi[i]*p;//性质二
            else phi[p*i]=phi[p]*phi[i];//性质三 
        }
    }
}

这种做法用到了上面的三种性质，复杂度为。