51Nod1136--欧拉函数-白红宇的个人博客

51Nod1136--欧拉函数

发布日期：2021-05-09 04:21:10 浏览次数：18 分类：博客文章

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

基准时间限制：1 秒空间限制：131072 KB 分值: 0

关注

对正整数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
             #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      using namespace std;typedef long long ll;#define Max 1000001int euler[Max];//筛法打素数表void Init(){ euler[1]=1; for(int i=2;i
                      
                       1) res=res/a*(a-1); return res;}int main(){ //Init(); int n; scanf("%d",&n); printf("%d\n",getEuler(n)); return 0;}

上一篇：HDU5804--Price List

下一篇：HDU2159--二维费用背包，三重背包

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章