MyException - 我的异常网
当前位置:我的异常网» 编程 » 小于等于N的全部整数与N关于gcd(i,N)的那些事

小于等于N的全部整数与N关于gcd(i,N)的那些事

www.MyException.Cn  网友分享于:2014-08-05  浏览:0次
小于等于N的所有整数与N关于gcd(i,N)的那些事

相关问题1: 求小于等于N的与N互质的数的和,即∑ i (gcd(i,N)=1, N>=i>0)

                  根据N的规模可以有很多种方法,这里我介绍一个比较经典的方法

 先说下这个结论:如果 gcd(n,i)=1则 gcd(n,n-i)=1 (1<=i<=n)
 这个非常好理解吧,对于任意两个数a,b a%s==0,b%s==0(a>b)

那么(a-b)%s肯定也是零。所以呢 gcd(n,i)==1则gcd(n,n-i)必须也为1 如果为s(s!=1)

那么gcd(n,n-(n-i))肯定也不是1啦
 于是问题变的非常简单
 ANS=N*phi(N)/2
 i,n-i总是成对出现,并且和是n
 下面的说明可以让你消除重复的疑虑
 因为:
 n=2*i->i=n/2
 1.如果n是奇数,那么n!=2*i,自然也不存在n-i=i和重复计算之说
 2.如果n是偶数,n=2*i成立,gcd(n,n/2)必然为n的一个因子,这个因子为1当且仅当n==2
 于是对于n>2的偶数,绝对不存在gcd(n,n/2)=1所以更别说什么重复计算了
 对于n==2
 ans=2*1/2=1
 正好也满足
 所以得到最终公式:
 ans=N*phi(N)/2

 

相关问题2:求gcd(i,N)的和,即∑gcd(i,N) ,(N>=i>0)

                 最直观的方法就是求N次gcd加起来,呵呵我开个玩笑的,N稍微大一点就没有用了。下面说说正规的解法吧

设函数g(n) = gcd(i,n) (1<=i<=n),对于任意给定的i 。 g(1) = 1 ,g(n)=g(m1)*g(m2) (n=m1*m2 且 (m1, m2)= 1),由积性函数定义,g是积性函数。由具体数学上的结论,积性函数的和也是积性的。所以f(n) = ∑gcd(i, n)也是积性函数。n>1时n可以被唯一分解 n=p1^a1*p2^a2*...*ps^as,由于f(n)是积所以f(n) = f(p1^a1)*f(p2^a2)*...f(pr^ar)。所以只要求f(pi^ai)就好,如果d是n的一个约数,那么1<=i<=n中gcd(i,n) = d的个数是phi(n/d),即n/d的欧拉函数

f(pi^ai) =  Φ(pi^ai)+pi*Φ(pi^(ai-1))+pi^2*Φ(pi^(ai-2))+...+pi^(ai-1)* Φ(pi)+ pi^ai *Φ(1)

     = pi^(ai-1)*(pi-1) + pi*pi^(ai-2)*(pi-1)....+pi^ai

     =  pi^ai*(1+ai*(1-1/pi))

接下来把各个项乘起来OK


相关问题3:求1到N的所有和N互质的数的乘积对N取模

               有这样的结论,对于1,2,4,答案为N-1,其余的4的倍数答案为1,质数答案为N-1,其余的若为偶数则除以2后再判断素因子的个数,奇数则直接判断,多余一个素因子答案为1,只有一个素因子答案为N-1; 相同的素因子不重复计数。

文章评论

10个调试和排错的小建议
10个调试和排错的小建议
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
程序员应该关注的一些事儿
程序员应该关注的一些事儿
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
鲜为人知的编程真相
鲜为人知的编程真相
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
漫画:程序员的工作
漫画:程序员的工作
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
中美印日四国程序员比较
中美印日四国程序员比较
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
我是如何打败拖延症的
我是如何打败拖延症的
编程语言是女人
编程语言是女人
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
总结2014中国互联网十大段子
总结2014中国互联网十大段子
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
老程序员的下场
老程序员的下场
那些争议最大的编程观点
那些争议最大的编程观点
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
一个程序员的时间管理
一个程序员的时间管理
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
 程序员的样子
程序员的样子
如何成为一名黑客
如何成为一名黑客
Java程序员必看电影
Java程序员必看电影
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
旅行,写作,编程
旅行,写作,编程
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
为什么程序员都是夜猫子
为什么程序员都是夜猫子
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
程序员都该阅读的书
程序员都该阅读的书
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
每天工作4小时的程序员
每天工作4小时的程序员
程序员必看的十大电影
程序员必看的十大电影
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有