欧拉函数的求法和递推式

一.φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn) pi为每一个质因数

 1 int cal(int m){
 2     if(m<=M)return phi[m];
 3     int ans=m;
 4     for(int i=1;i<=cnt && prime[i]*prime[i]<=m;i++){
 5         if(m%prime[i])continue;
 6         ans=ans/prime[i]*(prime[i]-1);
 7         while(m%prime[i]==0)m/=prime[i];
 8     }
 9     if(m>1)ans=ans/m*(m-1);
10     return ans;
11 }

二.对于任意一个能被n整除的质数，有m = n/p

当m%p == 0 的时候，phi(n) = phi(m)*p

当m%p != 0的时候，phi(n) = phi(m)*(p-1)

 1 void phim(){
 2     phi[1]=1;
 3     ll tmp;
 4     for(int i=2;i<=M;i++){
 5         if(!d[i]){
 6             prime[++cnt]=i;
 7             phi[i]=i-1;
 8         }
 9         for(int j=1;j<=cnt && (ll)prime[j]*i<=M;j++){
10             tmp=i*prime[j];
11             d[tmp]=true;
12             if(i%prime[j])phi[tmp]=phi[i]*(prime[j]-1);
13             else{
14                 phi[tmp]=phi[i]*prime[j];
15                 break;
16             }
17         }
18     }
19 }