9.筛法求欧拉函数

按照线性筛法求质数的方法，用O(n)的时间，求出1 ~ n中每一个数的欧拉函数

在线性筛的过程中，顺便求欧拉函数

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e6 + 10;
 4 typedef long long ll;
 5 int primes[N], cnt;
 6 bool st[N];
 7 int phi[N]; //欧拉函数
 8 ll get_eulers(int n) {
 9     phi[1] = 1;
10     for (int i = 2; i <= n; i++) {
11         if (!st[i]) {
12             primes[cnt++] = i;
13             //如果p这个数是质数的话，那么它的欧拉函数是p - 1
14             phi[i] = i - 1;
15         }
16         for (int j = 0; primes[j] <= n / i; j++) {
17             st[primes[j] * i] = true;
18             if (i % primes[j] == 0) {
19                 //此时primes[j] * i这个数的欧拉函数是
20                 phi[primes[j] * i] = phi[i] * primes[j];
21                 break;
22             }
23             //pj一定是pj * i的最小质因子,而且pj还不包含在i的质因子当中
24             phi[primes[j] * i] = phi[i] * (primes[j] - 1);
25         }
26     }
27     ll res = 0;
28     for (int i = 1; i <= n; i++) {
29         res += phi[i];
30     }
31     return res;
32 }
33 int main() {
34     int n;
35     cin >> n;
36     cout << get_eulers(n) << endl;
37     return 0;
38 }

欧拉函数有什么用处

有一个欧拉定理：

欧拉定理有一个推论：当n是质数的时候，如果a和n互质，则有

这个就是费马小定理，也就是牛客暑期多校训练里卡了我们队三个小时的定理