欧拉函数

\(φ(n)\) :定义：1~n中与n互质的数的个数(这里指的是gcd(i,n)=1的i,所以说phi[1]=1)

公式：

\[设N=p1^{α1}*p2^{α2}*p3^{α3}... \]

\[则\varphi(N)= N*(1-\frac{1}{p1})*(1-\frac{1}{p2})... \]

公式证明：

原理：容斥原理

从1~n中所有与N互质的数的个数

1.先从1~N中去掉p1,p2,...,pk的所有倍数
2.再加上所有\(p_i*p_j\)的倍数
3.再减去所有\(p_i*p_j*p_k\)的倍数
4.……

最后根据上面计算 总结出公式就是上面的式子了

筛法1

公式法

cin>>x;
long long ans=x;
for(int i=2;i*i<=x;i++){
    if(x%i==0){
        ans=ans/i*(i-1);
        x/=i;
        while(x%i==0) x/=i;
    }
}
if(x>1) ans=ans/x*(x-1);//先除后乘，防止溢出
cout<<ans<<endl;

时间复杂度：\(O(n\sqrt{n})\)

筛法2

先回忆一下线性筛

void prime(){
    for(int i=2;i<=N;i++){
        if(!vis[i]) prime[++num]=i;
        for(int j=1;j<=num&&i*prime[j]<N;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}

我们可以把这件求phi分成两步

k是质数

首先我们容易发现一个问题：如果\(k\)是质数，那么\(\varphi (k)\)显然等于\(k-1\)，因为小于\(k\)的数都与\(k\)互质

所以我们可以把这一句：if(!vis[i]) p[++num]=i;再加上一句phi[i]=i-1;

\(i\%p=0\)时

然后我们需要证明一个东西：

若\(p\mid i\)且\(p\)为质数 则 \(\varphi(i*p)\)=\(p*\varphi(i)\)

证明：

若\(p \mid i\) 则可以推出\(p\) 是 \(i\) 的一个质因子

我们发现：一个数的欧拉函数与每一项的次数无关

所以说

\[\varphi(i*p)=i*p*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})...*(1-\frac{1}{p_k}) \]

同时

\[\varphi(i)=i*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})...*(1-\frac{1}{p_k}) \]

发现两个式子除了\(i*p\)全部相同

所以我们可以推出 \(\varphi(i*p)\)=\(p*\varphi(i)\)

证毕

那么很显然在这一句中if(i%prime[j]==0) break;我们可以加上phi[prime[j]*i]=prime[j]*phi[i]

\(i\%p!=0\)时

\(p\)一定是\(i*p_j\)的最小质因子

先把\(\varphi(i)\)的式子摆在这

\[\varphi(i)=i*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})...*(1-\frac{1}{p_k}) \]

然后

\[\varphi(p*i)=p*i*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})...*(1-\frac{1}{p_k}*(1-\frac{1}{p})) \]

我们把下面的式子除以上面的式子发现：

\[\varphi(p*i)/\varphi(i)=p*(1-\frac{1}{p})=p-1 \]

把\(\varphi(i)\)挪到右边最后可以得到

\[\varphi(p*i)=\varphi(i)*(p-1) \]

所以我们讨论完了所有的情况，可以得到最终式子：

inline void get_euler(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            phi[i]=i-1;
            prime[++cnt]=i;
        }
        for(int j=1;prime[j]*i<=n && j<=cnt;j++){
            st[prime[j]*i]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=prime[j]*phi[i];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}