问题标题: 1590互质数

相关问题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; 相同的素因子不重复计数。