欧拉函数

$\phi(n)$即小于n且与n互素的整数个数。 由容斥定理可得公式： \(\phi(n)=\sum_{S\subseteq ( p_{1},p_{2},...,p_{k} ) }(-1)^{\left | S \right |}\frac{n}{\prod_{p_{i}\in S}p_{i}}\) 可经过化简得： \(\phi(n)=n(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})\cdots (1-\frac{1}{p_{k}})\)

单个求法：

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

求1~n中所有数的欧拉函数值（类似素数筛法）：

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

时间复杂度为$O(nloglogn)$。

欧拉函数

原文：https://www.cnblogs.com/sakyo/p/13751063.html