欧拉函数

欧拉函数记作phi（x）

对于一个数x他的欧拉函数的值就为所有比他小与且与他互质的数的个数

欧拉函数的通式：φ(n)=n*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…..(1-1/pn),其中p1, p2……pn为n的所有质因数，n是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。

int euler(int n)  
{  
    int ans=n;  
    for(int i=2;i*i<=n;i++){  
        if(n%i==0){  
            ans-=ans/i;  
            while(n%i==0){  
                n/=i;  
            }  
        }  
    }  
    if(n>1)ans-=ans/n;  
    return ans;  
}

欧拉函数的典型应用之一就是降幂 $a^{b}modx=a^{bmodphi(x)+phi(x))}modx$

另一个应用就是欧拉定理，也就是费马小定理的推广 $a^{phi(x)}modx=1$