基础数论--欧拉函数

在数论，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（因此φ(1)=1）

互质指的就是gcd(a,b)=1。

所以对于某个数n，求他的欧拉函数可以直接用暴力。

 1 int gcd(int a,int b){
 2     return b==0?a:gcd(b,a%b);
 3 }
 4 int get_phi(int n){
 5     int res=0;
 6     for(int i=1;i<=n;i++){
 7         if(gcd(i,n)==1){
 8             res++;
 9         }
10     }
11     return res;
12 }

但是这种方法时间复杂度为n*logn，显然过高，只能寻找其他方法

根据唯一分解定理，n=p1^a1*p1^a2...，只要将n的质因子的倍数都删掉，就是n的欧拉函数的值，这是因为如果某个数和n的约数不为1，那么这个约数也必然是n的因子

phi[n]=n-n/p1-n/p2-n/p3...

但是既是p1的倍数又是p2的倍数的数又被删了两遍（被p1删一遍，p2删一遍），把他们加上

phi[n]=n-n/p1-n/p2-n/p3...+n/p1p2+n/p2p3+...

而此时又多加一遍了同时是p1 p2 p3的倍数的数（p1+，p2+， p3+， p1p2-，p2p3-，p1p3- ）

这时候应该已经发现规律了，经过整理之后

phi[n]=n(1-1/p1)(1-1/p2)...

观察每一项可发现公式是正确的，代码实现

 1 int get_phi(int n){
 2     int res=n;
 3     for(int i=2;i<=n/i;i++){
 4         if(n%i==0){
 5             res=res/i*(i-1);//据唯一分解定理，这里的res/i一定是整除
 6             while(n%i==0){
 7                 n/=i;
 8             }
 9         }
10     }
11     if(n>1){
12         res=res/n*(n-1);
13     }
14     return res;
15 }

时间复杂度为sqrt(n)

有时候会有一种需求，就是求出1~n每个数的欧拉函数的值

如果用上述的方法，时间复杂度为n*sqrt(n)，1e6的数据救过不了了

这时候线性筛就派上用场了

线性筛代码：

 1 int get_primes(int n){
 2     for(int i=2;i<=n;i++){
 3         if(!st[i]){
 4             primes[cnt++]=i;
 5         }
 6         for(int j=0;primes[j]<=n/i;j++){
 7             st[primes[j]*i]=true;
 8             if(i%primes[j]==0) break;
 9         }
10     }
11     return cnt;
12 }

之前已经论证过了，线性筛中每一个数只会被筛到一次，并且不管 i 是合数或质数，在 i 的倍数之前 i 的状态一定被确定了

如果能够从 i 的phi值得出 pj * i 的phi值就解决了这个问题了

那么就需要用到以下性质和公式

1、如果p是质数，那么phi[p]=p-1

2、phi[n]=n(1-1/p1)(1-1/p2)...

 1 LL get_phis(int n){
 2     LL res=1;
 3     for(int i=2;i<=n;i++){
 4         if(!st[i]){
 5             primes[cnt++]=i;
 6             phi[i]=i-1;
 7             res+=phi[i];
 8         }
 9         for(int j=0;primes[j]<=n/i;j++){
10             st[primes[j]*i]=true;
11             if(i%primes[j]==0){
12                 phi[primes[j]*i]=primes[j]*phi[i];
13                 res+=phi[primes[j]*i];
14                 break;
15             }else{
16                 phi[primes[j]*i]=(primes[j]-1)*phi[i];
17                 res+=phi[primes[j]*i];
18             }
19         }
20     }
21     return res;
22 }

算法复杂度O(n)