欧拉函数

概念：欧拉函数用于解决1-n之间有多少数与n构成互质关系。

公式：

注解：pi为x的所有质因子，特别的要注意当x=1时，函数值为1。

证明：https://blog.csdn.net/wrwhahah/article/details/82704053

性质：

具体实现：

欧拉筛法：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<vector>
 4 #include<cstring>
 5 #include<cstdio>
 6 using namespace std;
 7 #define mem(s,n) memset(s,n,sizeof s);
 8 typedef long long ll;
 9 const int maxn=9e2+1;
10 const int Inf=0x7f7f7f7f;
11 bool isprime[maxn];
12 int prime[maxn];
13 int phi[maxn];
14 int cnt;
15 void eulor(int x)
16 {
17     phi[1]=1; //1单独处理;
18     cnt=0;
19     mem(isprime,1);
20     int tmp;
21     for(int i=2;i<=x;i++)
22     {
23         if(isprime[i]==1)
24         {
25             prime[++cnt]=i;
26             phi[i]=i-1; //i为质数情况;
27         }
28         for(int j=1;j<=cnt&&(tmp=i*prime[j])<=x;j++)
29         {
30             isprime[tmp]=0;
31             if(i%prime[j]==0)//此时的primes[j]是从小到大推出的第一个能整除i的质数，也就是primes[j]是i的质因子
32             {
33                 phi[tmp]=phi[i]*prime[j]; //情况1，若primes[j]是i的质因子，则根据计算公式，i已经包括i*primes[j]的所有质因子 
34                 break;
35             }
36             else
37             {
38                 phi[tmp]=phi[i]*phi[prime[j]];//情况2，否则两个因子互质了，就可以利用欧拉函数是积性函数的性质 
39             }
40         }
41     }
42 }
43 int main()
44 {
45     int n;
46     scanf("%d",&n);
47     eulor(n);
48     for(int i=1;i<=n;i++)
49     {
50         printf("%d ",phi[i]);
51     }
52     return 0;
53 }

View Code

常规法：

typedef long long ll;
ll phi(ll n) {
    ll ans = n;
    ll ma = sqrt(n);
    for (ll i = 2; i <= ma; i++) {
        if (n % i == 0) {
            ans = ans / i * (i - 1);
            while (n % i == 0)n /= i;
        }
    }
    if (n > 1)ans = ans / n * (n - 1);
    return ans;
}

View Code