数论-欧拉函数

欧拉函数：

时间复杂度：sqrt(n)

代码：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main(){
 5     int n;cin >> n;
 6     while(n --){
 7         int a;cin >> a;
 8         int res = a;
 9         for(int i = 2;i <= a/i;++i){
10             if(a % i == 0){
11                 res = res / i * (i - 1);//公式：i 分之 i - 1
12                 while(a % i == 0)a /= i;
13             }
14         }
15         if(a > 1)res = res / a * (a - 1);
16         cout << res << endl;
17     }
18     return 0;
19 }

View Code

线性筛欧拉函数：应用于让求 1 - n中每个数的欧拉函数，下面的代码是求和，背住

代码：

 1 #include <iostream> 
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 
 6 const int N = 1e6+10;
 7 
 8 int prime[N];
 9 bool st[N];
10 int ola[N];
11 int cnt;
12 int phi[N];
13 /*
14 void get_ola(ll n){
15     ola[1] = 1;
16     for(int i = 2;i <= n;++i){
17         if(!st[i]){
18             prime[cnt ++] = i;
19             ola[i] = i - 1;
20         }
21         for(int j = 0;prime[j] <= n/i;++j){
22             int t = i * prime[j];
23             st[t] = true;
24             if(i % prime[j] == 0){
25                 ola[t] = ola[i] * prime[j];
26                 break;
27             }
28             ola[t] = ola[i] * (prime[j] - 1);
29         }
30     }     
31 }
32 */
33 void phi_table(int n) {
34   for (int i = 2; i <= n; i++) phi[i] = 0;
35   phi[1] = 1;
36   for (int i = 2; i <= n; i++)
37     if (!phi[i])
38       for (int j = i; j <= n; j += i) {
39         if (!phi[j]) phi[j] = j;
40         phi[j] = phi[j] / i * (i - 1);
41       }
42 }
43 
44 int main(){
45     ll n;cin >> n;
46     get_ola(n);
47     phi_table(n);
48     ll ans = 0;
49     for(int i = 1;i <= n;++i) ans += phi[i];
50     cout << ans << endl;
51     return 0;
52 }

View Code