[总结] 欧拉函数

¶凉笙 · 2021-03-03 16:55:36 · 个人记录

一些概念

• 欧拉函数（Euler's totient function），即 \varphi(n) ，表示的是小于等于 n 和 n 互质的数的个数。

• 欧拉函数是积性函数，即对于满足 gcd(a,b)==1， f[a* b ]=f[a]* f [b]。特别地，当 n 是奇数时, f[2*n]=f[2]*f[n]

一些定理

• n=\sum_{d|n}\varphi(d)

• 除了 2 以外所有的 \varphi(n) 都是偶数

• \varphi (p^k)=p^k-p^{k-1}

暴力求得欧拉函数值

原理：一边分解一边按照下面的原理求解

int make_phi(int x){
    int phi=x;
    int t=(int)sqrt(x+0.5);
    for(int i=2;i<=t;i++){
        if(x%i==0){
            phi=phi-phi/i;
            while(x%i==0){
                x/=i;
            }
        }
    }
    if(x>1){
        phi=phi-phi/x;
    }
    return phi;
}

筛法构建欧拉函数表

原理：

• \varphi(n)=n*\Pi_{i=1}^s(1-\frac{1}{p_i})

inline void make_phi(int n){
    for(re int i=2;i<=n;i++)if(!phi[i])
        for(re int j=i;j<=n;j+=i){
            if(phi[j]==0)phi[j]=j;
            phi[j]=phi[j]/i*(i-1);
        }
}

应用

• 求 n 以内的与 n 互素的所有数的和

解法：ans=\varphi(n) * n/2