欧拉函数在解题的作用在于求一个数的质因子的个数，例如φ(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;
}
网友评论