欧拉函数模板

 1 int e(int n)
 2 {
 3     int cnt=n;
 4     int i;
 5     for(i=2;i<=n;i++)
 6         if(n%i==0)
 7         {
 8             cnt -=cnt/i;     
 9             while(n%i==0)
10                 n/=i;
11         }
12     return cnt;
13 }

View Code

E(x)为欧拉函数。P为N的一个质因子。

若(N%P==0 && (N/P)%P==0) 则有:E(N)=E(N/P)*P;

若(N%P==0 && (N/P)%P!=0) 则有:E(N)=E(N/P)*(P-1);

欧拉函数打表：

const int N=1e6+11;
int phi[N];
void init(){
    for(int i=2;i<N;i++){
        if(!phi[i]){
            for(int j=i;j<N;j+=i){
                if(!phi[j])    phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
        }
    }
}