51nod1136——欧拉函数-白红宇

51nod1136——欧拉函数

阅读量：2345 次

发布时间：2019-05-10

本文共 606 字，大约阅读时间需要 2 分钟。

对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler’s totient function、φ函数、欧拉商数等。例如：φ(8) = 4（Phi(8) = 4），因为1,3,5,7均和8互质。

Input

输入一个数N。(2 <= N <= 10^9)

Output

输出Phi(n)。

Input示例

Output示例

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #define INF 0x3f3f3f3f#define MAXN 100010using namespace std;int main(){ int n,ans; while(~scanf("%d",&n)) { ans=n; for(int i=2;i*i<=n;++i) { if(n==1) break; if(n%i==0) { ans=ans/i*(i-1); while(n%i==0) n/=i; } } if(n!=1) ans=ans/n*(n-1); printf("%d\n",ans); } return 0;}

转载地址：http://ticvb.baihongyu.com/

你可能感兴趣的文章