【算法學習筆記】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;
}