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

力的博客

小歇一会 heiheidemaolv

 
 
 

日志

 
 

怎样求互质数个数 ???  

2014-05-06 19:15:25|  分类: ACM/C/C++/OJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

给你一个数N,它只能被唯一分解成它的素因子乘积的形式,即N=p1^a1*p2^a2...pm^am,这里p1..pm是N的互异的素因子,从小到大,而ai则是N中pi的个数,比如18=2^1*3^2,36=2^2*3^3; 

       根据惟一分解定理,将N化成素因子乘积的形式之后,在N以内与之互素的整数的个数为:

       M=n*(1-1/p1)...(1-1/pm); 由于涉及精度的问题,我们将n代入括号内:for(i=1;i<=m;i++) n=n-n/p[i]; 循环结束后,n即为最终的结果:与之互质的数的个数。

如何理解这一定理:

       题目要求的是与N互质的数的个数,即这些数中都不包括N的素因子,因此,反过来想,如果我们将[1,N]内的所有N的素因子的倍数都删除掉之后,那么余下的数不就是我们要求的数了吗?以下是这一想法的具体实现过程:为便于大家理解,我将n具体化,设n=12;则通过筛选法求出它的两个素因子2,3,[1,12]内2的倍数为12/2=6,因此12-6=6;将2的倍数全部删除,然后再在余下的6个数中删除3的倍数6-6/3=4,素因子已用完,4即为最后结果,用定理描述就是:M=12*(1-1/2)*(1-1/3),此定理与此想法不谋而合。

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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