上节学习的是求一个数 n n n的欧拉函数，由于用的试除法，所以时间复杂度是 O ( n ) O(\sqrt{n}) O(n )，如果要求 m m m个数的欧拉函数，那么就会花 O ( m n ) O(m \sqrt{n}) O(mn )的时间。如果是求一连一批数的欧拉函数，可以用筛法进行优化。
筛法求欧拉函数原理
在线性筛求质数时可以顺便把每个数的欧拉函数筛出来。根据线性筛过程，一个数要么是质数被pick出来，要么是合数被筛掉，一共有如许三个地方：
- 从筛子（st数组）里发现 i i i是一个质数
- 合数 p r i m e s [ j ] ∗ i primes[j] * i primes[j]∗i被筛掉，此中质数 p r i m e s [ j ] primes[j] primes[j]同时也是 i i i的质因子（按照线性筛，也肯定是最小质因子）
- 合数 p r i m e s [ j ] ∗ i primes[j] * i primes[j]∗i被筛掉，此中质数 p r i m e s [ j ] primes[j] primes[j]不是 i i i的质因子（仅仅是 p r i m e s [ j ] ∗ i primes[j] * i primes[j]∗i的最小质因子）
三种环境合起来就不多不少地包罗了从 1 1 1到 n n n的所有数字。
- 对于环境1，质数 i i i的欧拉函数根据定义就是除了 i i i之外的那 i − 1 i - 1 i−1个数，由于它们肯定都和 i i i互质，所以 ϕ ( i ) = i − 1 \phi(i) = i - 1 ϕ(i)=i−1
- 对于环境2，由于 p r i m e s [ j ] primes[j] primes[j]也是 i i i的质因子，根据欧拉公式，除了第一项外剩下那些用1减的项，都只和质因子有关，和质因子的指数无关，因此相比 ϕ ( i ) \phi(i) ϕ(i)， ϕ ( p r i m e s [ j ] ∗ i ) \phi(primes[j] * i) ϕ(primes[j]∗i)只有第一项从 i i i酿成了 p r i m e s [ j ] ∗ i primes[j] * i primes[j]∗i
- 对于环境3，由于 p r i m e s [ j ] primes[j] primes[j]是一个质数而且和 i i i互质，因此 ϕ ( p r i m e s [ j ] ∗ i ) \phi(primes[j] * i) ϕ(primes[j]∗i)的公式里，除了第一项要酿成 p r i m e s [ j ] ∗ i primes[j] * i primes[j]∗i，还由于添加了一个新的质数 p r i m e s [ j ] primes[j] primes[j]所以要乘以一个 1 − 1 p r i m e s [ j ] 1 - \frac{1}{primes[j]} 1−primes[j]1，所以总共要乘以 p r i m e s [ j ] − 1 primes[j] - 1 primes[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;
- }
|
