nefu1010裸的欧拉函数

和这几天做的题比简直太小儿科了==

欧拉函数是指：对于一个正整数n，小于n且和n互质的正整数（包括1）的个数，记作φ(n)。（互质：公约数只有1的两个整数，叫做互质整数。唯一和1互质的数就是1本身）
欧拉函数的性质：它在整数n上的值等于对n进行素因子分解后，所有的素数幂上的欧拉函数之积。
通式：φ(x)=x*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…..(1-1/pn),其中p1,p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。（X=(p1^a1)*(p2^a2)*(p3^a3)*(p3^a3)……*(pk^ak)
对于质数p，φ(p) = p - 1。注意φ(1)=1.
欧拉定理：对于互质的正整数a和n，有a^φ(n) ≡ 1 mod n。
欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。
特殊性质：当n为奇数时，φ(2n)=φ(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)。
然后附上代码：
#include   //欧拉之实现 
using namespace std; 
int main() 
{    inti,n,m; 
   while(cin>>n) 
   { 
       m=n; 
       for(i=2;i*i<=n;i++) //因为任何一个合数都至少有一个不大于根号n的素因子，故只需要遍历到根号n即可
       { 
           if(n%i==0) 
           { 
               m=m/i*(i-1);  //先进行除法是为了防止中间数据的溢出
                             //m-=m/i;      m-m/p    m/i为能被i整除的所有小于等于n的整数。减去其数量
               while(n%i==0) 
               { 
                   n/=i;  //   把i为素因子全部约掉。
               } 
           } 
       } 
       if(n>1) m=m/n*(n-1);  //先进行除法是为了防止中间数据的溢出
       cout<<m<<endl; 
   } 
    return0; 
}