//直接求解歐拉函數(shù)??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);//先進(jìn)行除法是為了防止中間數(shù)據(jù)的溢出???
?????????????while(a%i==0)?a/=i;??
?????????}??
?????}??
?????if(a>1)?res=res/a*(a-1);??
?????return?res;??
}??//篩選法打歐拉函數(shù)表???#define?Max?1000001??int?euler[Max];??void?Init(){???
?????euler[1]=1;??
?????for(int?i=2;i<Max;i++)??
???????euler[i]=i;??
?????for(int?i=2;i<Max;i++)??
????????if(euler[i]==i)??
???????????for(int?j=i;j<Max;j+=i)??
??????????????euler[j]=euler[j]/i*(i-1);//先進(jìn)行除法是為了防止中間數(shù)據(jù)的溢出???}