c++ - 所有数的最大公约数之和，直到 n 与 n

Question

从1到n有n个数。我需要找到 ∑gcd(i,n) 其中 i=1 到 i=n 对于范围 10^7 的 n。我对 gcd 使用了 euclid 的算法，但它给出了 TLE。有什么有效的方法可以找到上面的总和吗？

#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;
}

Answer 1

您可以通过批量 GCD 计算来完成。 您应该找到所有简单的除数和这些除数的幂。这可以在 Sqtr(N) 复杂度中完成。 在需要后组成 GCD 表。

可能是C#上的代码片段，转换成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 次方。

例如如果 n = 125

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

如果 n = 12

• p = [2,3]
• c = [2,1]
• 12 = 2^2 * 3^1