大家好，又见面了，我是你们的朋友全栈君。
话说我以前求这样的问题都是先求与N不互质的数，把N分解质因数，然后用容斥原理，今天看了大牛的博客，顿时觉得弱爆了。。。
以下内容转大牛文章：
if gcd(n,i)=1 then gcd(n,n-i)=1 (1<=i<=n)
反证法：
如果存在K!=1使gcd(n,n-i)=k,那么(n-i)%k==0
而n%k=0
那么必须保证i%k=0
k是n的因子,如果i%k=0那么gcd(n,i)=k,矛盾出现;
于是问题变的非常简单
ANS=N*phi(N)/2
i,n-i总是成对出现，并且和是n
于是可能就有人问了，如果存在n-i=i那不是重复计算？
答案是不会
因为:
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
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/163380.html原文链接：https://javaforall.net
