筛法求欧拉函数

欧拉函数

$1$ ~ $n$ 中与 $n$ 互质的数的个数叫做欧拉函数，记作 $\varphi (n)$

有性质如下：

• 存在质数 $p$ ，则 $\varphi(p)=p-1$
• 存在质数 $p$ ，则 $\varphi(p^k)=(p-1)p^{k-1}$

于是可以推出欧拉函数的计算公式，根据惟一分解定理有

$$ n=\prod_{i=1}^sp_i^{\alpha_i}=p_1^{\alpha_1}p_2^{\alpha_2} \dots p_s^{\alpha_s} $$

于是欧拉函数可以写为

$$ \varphi(n)=\prod_{i=1}^s\varphi(p_i^{s_i}) = \prod_{i=1}^s(p_i-1)p_i^{\alpha_i-1} $$

$$ \Rightarrow\varphi(n)=\prod_{i=1}^sp_i^{\alpha_i}(1-\frac{1}{p_i}) =\prod_{i=1}^sp_i^{\alpha_i}\times \prod_{i=1}^s(1-\frac{1}{p_i}) $$

整理后得到

$$ \varphi(n)=n\times\prod_{i=1}^s\frac{p_i-1}{p_i}=n\times \frac{p_1-1}{p_1}\times\frac{p_2-1}{p_2}\times\dots\times\frac{p_s-1}{p_s} $$

观察上式可以发现欧拉函数只和 $n$ 与它的质因子有关

试除法求欧拉函数

从小到大枚举 $\sqrt{n}$ 的质因子，计算 $\frac{p_i-1}{p_i}$ ，然后在 $n$ 中除掉这个质因子的所有贡献

long long get_phi(int n){
    long long res = n;
    for (long long i = 2; i * i <= n; i++){
        if (n % i == 0){//判断i是否为n的质因子
            res = res * (i - 1) / i;//计算欧拉函数的部分
            while (n % i == 0) //把n中的这个质因子除干净
                n /= i;
        }
    }
    if (n > 1) res = res * (n - 1) / n;/如果最后剩余的n大于1，那么n就是最后的一个最大质因子
    return res;
}

if (n > 1) res = res * (n - 1) / n; 加上这句判断的原因是：一个整数 $n$ 最多仅有一个超过 $\sqrt n$ 的质因子

筛法求欧拉函数

通过线性筛法计算从 $1$ ~ $n$ 之间每个数的欧拉函数，以下是欧拉函数的另一个性质：

• 若有 $gcd(m,n)=1$ （$m,n$互质），则 $\varphi(mn)=\varphi(m)\times\varphi(n)$

int p[N], vis[N], cnt;
int phi[N];

void get_phi(int n){
    for (int i = 2, i <= n; i++){
        if (!vis[i]){
            p[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; i * p[j] <= n; j++){
            int m = i * p[j];
            vis[m] = 1;
            if (i % p[j] == 0){
                phi[m] = p[j] * phi[i];
                break;
            }
            else
                phi[m] = (p[j] - 1) * phi[i];
        }
    }
}

如果枚举的 $i$ 为质数，那么 $\varphi(i)=i-1$

//vis[i]==0
phi[i] = i - 1;

枚举的 $i$ 为合数（此时的 $i$ 已被之前的质因子筛到过），那么存在两种情况，可以向后递推合数

• 筛到的 $m$ 可以写作 $i*p_j$ ，如果 $i$ 能被 $p_j$ 整除，说明 $\varphi(m)=\varphi(i)$（$i$ 存在 $m$ 的所有质因子）
• 如果 $i$ 不能被 $p_j$ 整除，说明 $i,p_j$ 互质，那么 $\varphi(m)=\varphi(i)*\varphi(p_j)$

如果只需要求单个数的欧拉函数，试除法比筛法更加优秀