数论 欧拉函数

欧拉函数在解题的作用在于求一个数的质因子的个数，例如φ(24)=8，因为1, 5, 7, 11, 13, 17, 19, 23均和 24 互质。欧拉函数的公式为：

Φ(N)=N(1-1/P1)(1-1/P2)(1-1/P3)....(1-1/Pn);

P1，P2，P3……都是N的质因子。

可以快速求出欧拉函数的值（a为N的质因素）　　若( N%a ==0&&(N/a)%a ==0)则有：E(N)= E(N/a)a;　　若( N%a ==0&&(N/a)%a !=0)则有：E(N)= E(N/a)(a-1);

欧拉函数的线性打表法：欧拉函数线性打表法：

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