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

上节学习的是求一个数                                   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. 筛法求欧拉函数

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

1. #include <iostream>
3. using namespace std;
5. typedef unsigned long long ULL;
7. const int N = 1e6 + 10;
9. int primes[N], cnt;
10. bool st[N];
11. int eulars[N];
13. int main() {
14.     int n; cin >> n;
15.    
16.     eulars[1] = 1;
17.     for (int i = 2; i <= n; i ++ ) {
18.         if (!st[i]) {
19.             primes[cnt ++ ] = i;
20.             // i是质数，从1到i-1都和i互质
21.             eulars[i] = i - 1;
22.         }
23.         for (int j = 0; primes[j] * i <= n; j ++ ) {
24.             st[primes[j] * i] = true;
25.             if (i % primes[j] == 0) {
26.                 // primes[j]是i的质因子，欧拉公式里只要变第一项
27.                 eulars[primes[j] * i] = eulars[i] * primes[j];
28.                 break;
29.             }
30.             // primes[j]不是i的质因子，欧拉公式里要变第一项和(1-1/primes[j])那项
31.             eulars[primes[j] * i] = eulars[i] * (primes[j] - 1);
32.         }
33.     }
34.    
35.     ULL res = 0;
36.     for (int i = 1; i <= n; i ++ ) {
37.         res += eulars[i];
38.     }
39.     cout << res << endl;
40.    
41.     return 0;
42. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告