欧拉函数

欧拉函数：
在数论中，对正整数n，欧拉函数 ϕ(n) 是小于或等于n的正整数中与n互质的数的数目。

对于素数p, φ(p)=p-1，对于对两个素数p,q φ（pq）=pq-1；
　除了N=2,φ(N)都是偶数.

1）.

原理：φ(n)=n*（1-1/p1)(1-1/p2)....(1-1/pk),其中p1、p2…pk为n的所有质因子。

//直接求解欧拉函数  
int euler(int n){ //返回euler(n)   
     int res=n,a=n;  
     for(int i=2;i*i<=a;i++){  
         if(a%i==0){  
             res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出   
             while(a%i==0) a/=i;  
         }  
     }  
     if(a>1) res=res/a*(a-1);  
     return res;  
}

2).
更好的算法，一次求出所有的euler[]：

 1 筛法求欧拉函数
 2 void Init(){     
 3      euler[1]=1;    
 4      for(int i=2;i<Max;i++)    
 5        euler[i]=i;    
 6      for(int i=2;i<Max;i++)    
 7         if(euler[i]==i)    
 8            for(int j=i;j<Max;j+=i)    
 9               euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出     
10 }

3).

假设当前从ϕ(i),ϕ(pt)转移到ϕ(ipt)：
1、如果pt是在ipt中第一次出现的话(也就是pt不整除i)，则ϕ(ipt)=ϕ(i)(pt−1)
2、如果pt不是在ipt中第一次出现的话(也就是pt整除i)，则ϕ(ipt)=ϕ(i)pt

 1 线性筛法求欧拉函数：
 2 int tot=0;
 3 int phi[maxn],prime[maxn];
 4 bool isPrime[maxn];
 5 void getphi(){
 6     mem(isPrime,true);
 7     phi[1]=1;
 8     for(int i=2;i<=maxn;i++){
 9         if(isPrime[i]) prime[++tot]=i,phi[i]=i-1;
10         for(int j=1;j<=tot;j++){
11             if(i*prime[j]>maxn) break;
12             isPrime[i*prime[j]]=false;
13             if(i%prime[j]==0){
14                 phi[i*prime[j]]=phi[i]*prime[j];
15                 break;
16             }else phi[i*prime[j]]=phi[i]*(prime[j]-1);
17         }
18     }
19 }