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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

欧拉函数  

2012-12-19 12:37:46|  分类: ACM-Steps |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |



欧拉函数介绍以及几条性质:

欧拉函数的通式:φ(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本身)。 (注意:每种质因数只一个,比如12=2*2*3)

那么φ(12)=12*(1-1/2)*(1-1/3)=4)。

几条性质:

φ(m*n)=φ(m)*φ(n),gcd(m,n)==1;

φ(p^k)=(k-1)*p^(k-1);

φ(n)=n-1,n为质数

当n为奇数时,φ(2n)=φ(n)


打欧拉函数表函数写法:

打欧拉函数表的做法和素数筛选法很像,所以这里一起把素数和欧拉函数值都打出来了,如果有不需要用素数表,则可以省略

#define N 1000000
__int64 prime[N];//存素数
bool f[N];
__int64 Ou[N+2];//存欧拉函数

void fun()
{
// //打素数表和欧拉函数表,前N个
__int64 i,j,pNum=0;
memset(f,false,sizeof(f));
Ou[1]=1;
for(i=2;i<=N;i++)
{
if(!f[i])
{
prime[pNum++]=i;
Ou[i]=i-1;
}
for(j=0;j<pNum && prime[j]*i<=N;j++)
{
f[prime[j]*i]=true;
if(i%prime[j]==0)
{
Ou[i*prime[j]]=Ou[i]*prime[j];
break;
}
else
Ou[i*prime[j]]=Ou[i]*(prime[j]-1);
}
}

//下面求的素数表和欧拉函数表,是根据欧拉函数定义来求解,上面部分是经过改进后的求法(效率较高)
// __int64 i,j,pNum=0;
// memset(f,true,sizeof(f));
// f[0]=f[1]=false;
// for(i=2;i*i<=N;i++)
// if(f[i])
// for(j=i*i;j<=N;j+=i)
// f[j]=false;
// for(i=1;i<=N;i++)
// Ou[i]=i;
// for(i=2;i<=N;i++)
// if(f[i])
// {
// prime[pNum++]=i;//如果不需要素数表,可以把这步省去
// for(j=i;j<=N;j+=i)//根据欧拉函数的定义来更新
// Ou[j]=Ou[j]/i*(i-1);
// }
}


欧拉函数值前20个:

i

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

φ(i)

1

1

2

2

4

2

6

4

6

4

10

4

12

6

8

8

16

6

18

8


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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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