所有数字的最大公约数除以n与n [英] Sum of Greatest Common Divisor of all numbers till n with n

问题描述

从1到n有n个数字。我需要找到
Σgcd（i，n），其中i = 1到i = n
，对于范围10 ^ 7的n。我使用euclid的算法gcd，但它给了TLE。有什么有效的方法找到上述和？

There are n numbers from 1 to n. I need to find the ∑gcd(i,n) where i=1 to i=n for n of the range 10^7. I used euclid's algorithm for gcd but it gave TLE. Is there any efficient method for finding the above sum?

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
   ll n,sum=0;
   scanf("%lld",&n);
   for(int i=1;i<=n;i++)
   {
       sum+=gcd(i,n);
   }
   printf("%lld\n",sum);
   return 0;
}

推荐答案

GCD计算。
你应该找到所有简单的除数和这些除数的幂。这可能在Sqtr（N）复杂度中完成。
在必要之后编写GCD表。

You can do it via bulk GCD calculation. You should found all simple divisors and powers of these divisors. This is possible done in Sqtr(N) complexity. After required compose GCD table.

可以在C＃上编译代码片段，不难将其转换为C ++

May code snippet on C#, it is not difficult to convert into C++

int[] gcd = new int[x + 1];
for (int i = 1; i <= x; i++) gcd[i] = 1;
for (int i = 0; i < p.Length; i++)
    for (int j = 0, h = p[i]; j < c[i]; j++, h *= p[i])
        for (long k = h; k <= x; k += h)
            gcd[k] *= p[i];

long sum = 0;
for (int i = 1; i <= x; i++) sum += gcd[i];

p它是简单除数的数组和该除数的c次方。

p it is array of simple divisors and c power of this divisor.

例如，如果n = 125

For example if n = 125

• p = [5]
li> c = [3]

• 125 = 5 ^ 3

• p = [5]
• c = [3]
• 125 = 5^3

• p = [2,3]


• c = [2,1]


• 12 = 2 ^ 2 * 3 ^ 1

这篇关于所有数字的最大公约数除以n与n的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！