【算法学习笔记】32：筛法求解欧拉函数

上节学习的是求一个数 $n$ 的欧拉函数，因为用的试除法，所以时间复杂度是 $O(\sqrt{n})$ ，如果要求 $m$ 个数的欧拉函数，那么就会花 $\sqrt{n})$ 的时间。如果是求连续一批数的欧拉函数，可以用筛法进行优化。

筛法求欧拉函数原理

在线性筛求质数时可以顺便把每个数的欧拉函数筛出来。根据线性筛过程，一个数要么是质数被pick出来，要么是合数被筛掉，一共有这样三个地方：

从筛子（st数组）里发现 $i$ 是一个质数
合数 $p r im es [j] * i$ 被筛掉，其中质数 $p r im es [j]$ 同时也是 $i$ 的质因子（按照线性筛，也一定是最小质因子）
合数 $p r im es [j] * i$ 被筛掉，其中质数 $p r im es [j]$ 不是 $i$ 的质因子（仅仅是 $p r im es [j] * i$ 的最小质因子）

三种情况合起来就不多不少地包含了从 $1$ 到 $n$ 的所有数字。

对于情况1，质数 $i$ 的欧拉函数根据定义就是除了 $i$ 之外的那 $i - 1$ 个数，因为它们一定都和 $i$ 互质，所以 $\phi(i) = i - 1$
对于情况2，因为 $p r im es [j]$ 也是 $i$ 的质因子，根据欧拉公式，除了第一项外剩下那些用1减的项，都只和质因子有关，和质因子的指数无关，因此相比 $\phi(i)$ ， $\phi(primes[j] * i)$ 只有第一项从 $i$ 变成了 $p r im es [j] * i$
对于情况3，因为 $p r im es [j]$ 是一个质数而且和 $i$ 互质，因此 $\phi(primes[j] * i)$ 的公式里，除了第一项要变成 $p r im es [j] * i$ ，还因为添加了一个新的质数 $p r im es [j]$ 所以要乘以一个 $\frac{1}{primes[j]}$ ，所以总共要乘以 $p r im es [j] - 1$

例题：AcWing 874. 筛法求欧拉函数

只要利用线性筛的模板和上面的结论，在三个地方填空即可。

#include <iostream>

using namespace std;

typedef unsigned long long ULL;

const int N = 1e6 + 10;

int primes[N], cnt;
bool st[N];
int eulars[N];

int main() {
    int n; cin >> n;
    
    eulars[1] = 1;
    for (int i = 2; i <= n; i ++ ) {
        if (!st[i]) {
            primes[cnt ++ ] = i;
            // i是质数，从1到i-1都和i互质
            eulars[i] = i - 1;
        }
        for (int j = 0; primes[j] * i <= n; j ++ ) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) {
                // primes[j]是i的质因子，欧拉公式里只要变第一项
                eulars[primes[j] * i] = eulars[i] * primes[j];
                break;
            }
            // primes[j]不是i的质因子，欧拉公式里要变第一项和(1-1/primes[j])那项
            eulars[primes[j] * i] = eulars[i] * (primes[j] - 1);
        }
    }
    
    ULL res = 0;
    for (int i = 1; i <= n; i ++ ) {
        res += eulars[i];
    }
    cout << res << endl;
    
    return 0;
}