欧拉函数 学习笔记

数学 数论

---

定义：

$1 \sim N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $\varphi (N)$。

计算式：

若根据算数基本定理，$N=p_1^{c_1}p_2^{c_2}p_3^{c_3}\cdots p_k^{c_k}$，则

$$\varphi(N)=N*\frac {p_1-1}{p_1}*\frac {p_2-1}{p_2}*\frac {p_3-1}{p_3}*\cdots *\frac {p_k-1}{p_k}=N*\Pi_{i=1}^{k}(\frac {p_i-1}{p_i})=N*\Pi_{i=1}^{k}(1-\frac {1}{p_i})$$

计算方法：

根据计算式可知，我们只需分解质因数，就可以顺便求出欧拉函数。

int Euler(int n)｛
    int ans=n;
    for(int i=2;i<=sqrt(n);i++){
        if(n%i) continue;
        ans=ans/i*(i-1);
        while(n%i==0) n/=i;
    }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}