GCD - Extreme (II)

UVA - 11426

Given the value of $N$, you will have to find the value of $G$. The definition of $G$ is given below:

Here $\gcd(i,j)$ means the greatest common divisor of integer $i$ and integer $j$.

For those who have trouble understanding summation notation, the meaning of $G$ is given in the following code:

1
2
3
4
5
6
7
G=0;
for(i=1;i<N;i++)
for(j=i+1;j<=N;j++)
{
    G+=gcd(i,j);
}
/*Here gcd() is a function that finds the greatest common divisor of the two input numbers*/

Input

The input file contains at most $100$ lines of inputs. Each line contains an integer $N$ ($1<N<4000001$). The meaning of $N$ is given in the problem statement. Input is terminated by a line containing a single zero.

Output

For each line of input produce one line of output. This line contains the value of $G$ for the corresponding $N$. The value of $G$ will fit in a 64-bit signed integer.

Sample Input

1
2
3
4
10
100
200000
0

Sample Output

1
2
3
67
13015
143295493160

题意

给你一个 $N$，让你计算题面中式子的值。

解决方案

此题乍一看，首先就是想到一个 $O(n^2\log n)$ 的暴力算法，显然不行。我们想想在 $4e6$ 的范围内，两个不同的数的 $\gcd$ 也是在 $4e6$ 范围内的，那能不能通过枚举 $\gcd$ 来计算？

考虑一个数 $n$ ，$n$ 的一个因子 $k$ ，那么，小于 $n$ 且与 $n$ 的 $gcd$ 为 $k$ 的数有多少个？我们设其中一个数为 $a$，则显然有 $\gcd(a/k, n/k) = 1$ ，为啥？

假设 $\gcd(a/k, n/k)=g,$ ，又 $gcd(n, n/k) = n/k$，所以

$gcd(a, n) = gcd(k\times a/k,k\times n/k)=k\times \gcd(a/k, n/k) = k\times g$，若要 $\gcd(a,n)=k$，则必有 $g=1$，即 $n/k$ 与 $a/k$ 互质，因为 $a < n$，所以 $a/k < n/k$，所以 $a$ 的数量就是 $[1, n/ k)$ 内与 $n/k$ 互质的数的数量。

结论，在$[1,n)$ 的范围内，与 $n$ 的 $\gcd$ 为 $k$ 的数共有 $\phi(n/k)$ 个， $\phi$ 为欧拉函数。

接下来就是枚举 $k$ ，用 $n\ln n$ 的筛打表，最终时间复杂度也是 $O(n\log n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 4e6 + 10;

bool vis[maxn];
int prime[maxn];
int phi[maxn];
ll sum[maxn];
int tot;

void eular() {
  phi[1] = 1;
  for (int i = 2; i < maxn; i++) {
    if (!vis[i]) {
      prime[tot++] = i;
      phi[i] = i - 1;
    }
    for (int j = 0; j < tot && i * prime[j] < maxn; j++) {
      vis[i * prime[j]] = true;
      phi[i * prime[j]] = phi[i] * (prime[j] - 1);
      if (i % prime[j] == 0) {
        phi[i * prime[j]] = phi[i] * prime[j];
        break;
      }
    }
  }
}

int main() {
  eular();
  for (int i = 1; 2 * i < maxn; i++) {
    for (int j = 2 * i; j < maxn; j += i) {
      sum[j] += i * phi[j / i];
    }
  }
  for (int i = 1; i < maxn; i++) {
    sum[i] += sum[i - 1];
  }
  int n;
  while (scanf("%d", &n) && n) {
    printf("%lld\n", sum[n]);
  }
  return 0;
}