Problem H
GCD Extreme
Input: Standard Input

Output: Standard Output

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:

Input

The input file contains at most 20000 lines of inputs. Each line contains an integer N (1<N<200001). 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                              Output for Sample Input

Problemsetter: Shahriar Manzoor and Syed Monowar Hossain

Special Thanks: Shahriar Manzoor and Syed Monowar Hossain

背景知識：phi(n) = 小於等於 n 且與 n 互質的個數

題目須要稍微轉換一下，

對於一個數字 n，求 sigma(gcd(n, i)) = ? (i < n)

但這樣還不是很好算, 因此如果我們假設 g = gcd(n, i), 對於一個 g 我們能知道使用了幾次，

已知 gcd(m, i) = 1 的個數 = phi(m), 等價 gcd(m*g, i) = 1*g 的個數 phi(m)

因此只要找到 m = n/g 即可。

先用 sieve 計算 phi(), 然後先枚舉所有可能 g(1~maxn) 對應的 n。

如果先枚舉 n 再枚舉 g(所有因數) 則會太慢。

#include <stdio.h>
#include <algorithm>
using namespace std;
#define maxL (200000>>5)+1
#define GET(x) (mark[(x)>>5]>>((x)&31)&1)
#define SET(x) (mark[(x)>>5] |= 1<<((x)&31))
int mark[maxL];
int phi[200005];
long long dp[200005];
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 200000;
    for(i = 2; i <= n; i++)
        phi[i] = i;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            phi[i] = phi[i]/i*(i-1);
            for(k = n/i, j = i*k; k >= 2; k--, j -= i) {
                SET(j);
                phi[j] = phi[j]/i*(i-1);
            }
        }
    }
}
int main() {
    sieve();
    int n;
    register int i, j, *k;
    for(i = 1; i <= 200000; i++) { // gcd(n, ?) = i
        k = phi+2;
        for(j = i+i; j <= 200000; j += i) {// j = n
            //dp[j] += i*phi[j/i];
            dp[j] += i*(*k);
            k++;
        }
    }
    for(i = 1; i <= 200000; i++)
        dp[i] += dp[i-1];
    while(scanf("%d", &n) == 1 && n) {
        printf("%lld\n", dp[n]);
    }
    return 0;
}