注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

qus的博客

 
 
 

日志

 
 

欧拉函数  

2009-08-10 21:41:23|  分类: 资料 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

欧拉函数  在数论,对正整数n,欧拉函数是少于或等于n的数中与n互质的数

的数目。此函数以其首名研究者欧拉命名,它又称为Euler's totient function

、φ函数、欧拉商数等。
  例如φ(8)=4,因为1,3,5,7均和8互质。
  从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证

明。
  φ函数的值
  φ(1)=1(唯一和1互质的数就是1本身)。
  若n是质数p的k次幂,φ(n)=p^k-p^(k-1)=(p-1)p^(k-1),因为除了p的倍数

外,其他数都跟n互质。
  欧拉函数是积性函数——若m,n互质,φ(mn)=φ(m)φ(n)。
  证明:设A, B, C是跟m, n, mn互质的数的集,据中国剩余定理,A*B和C可

建立一一对应的关系。因此φ(n)的值使用算术基本定理便知,
  若
  n= ∏p^(α(下标p))
  p|n
  则φ(n)=∏(p-1)p^(α(下标p)-1)=n∏(1-1/p)
  p|n p|n
  例如φ(72)=φ(2^3×3^2)=(2-1)2^(3-1)×(3-1)3^(2-1)=24
  与欧拉定理、费马小定理的关系
  对任何两个互质的正整数a, m, m>=2有
  a^φ(m)≡1(mod m)
  即欧拉定理
  当m是质数p时,此式则为:
  a^(p-1)≡1(mod m)
  即费马小定理。

#include<iostream>
#define MAXL 1000000
using namespace std;
__int64 x[MAXL+100];//记录欧拉函数值
bool used[MAXL+100];//判断质数
int z[MAXL];//存储质数
int zl;
void init()
{
 int i,j;
 memset(used,false,sizeof(used));
 zl=0;
 x[1]=1;
 for(i=2;i<=MAXL;i++)
 {
  if(!used[i])
  {
   z[zl++]=i;
   x[i]=i-1;
  }
  for(j=0;j<zl&&z[j]*i<=MAXL;j++)
  {
   used[i*z[j]]=true;
   if(i%z[j]==0)
   {
    x[i*z[j]]=x[i]*z[j];
    break;
   }
   else
   {
    x[i*z[j]]=x[i]*(z[j]-1);
   }
  }
 }
}

  评论这张
 
阅读(127)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017