题意很简单 就是欧拉函数的定义：

欧拉函数是指：对于一个正整数n，小于n且和n互质的正整数（包括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的整数

然后利用以下性质变形：

 

欧拉函数是——若m,n互质，φ(mn)=φ(m)φ(n)。

                                 若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。

最后 就是 先把 题目给的 n 进行素因子分解 n=pi^mi*......*pj^mj,求φ(n)其实按照积极函数性质一 φ(n)=φ(pi^mi*)*.....*φ(pj^mj),然后分别求出 φ(pi^mi*)  根据积极函数的性质二    φ(pi^mi)  =(pi-1)*pi^(mi-1)

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include