uva 11426 - GCD - Extreme (II)(數論)

題目鏈接：uva 11426 - GCD - Extreme

題目大意：給出n，求∑i!=jngcd(i,j)

解題思路：f(n)=gcd(1,n)+gcd(2,n)+?+gcd(n?1,n)
S(n)=f(2)+f(3)+?+f(n)
S(n)=S(n?1)+f(n)
問題轉化成怎麼求f(n),對於一個n來說，枚舉因子乘上個數即可。

#include 
#include 

const int N = 4000000;
typedef long long ll;

int phi[N+5];
ll s[N+5], f[N+5];

void phi_table(int n) {
    for (int i = 2; i <= n; i++)
        phi[i] = 0;
    phi[1] = 1;

    for (int i = 2; i <= n; i++) {
        if (!phi[i]) {
            for (int j = i; j <= n; j += i) {
                if (!phi[j])
                    phi[j] = j;
                phi[j] = phi[j] / i * (i-1);
            }
        }
    }
}

int main () {
    phi_table(N);

    memset(f, 0, sizeof(f));
    for (int i = 1; i <= N; i++) {
        for (int j = i * 2; j <= N; j += i) {
            f[j] += i * phi[j/i];
        }
    }
    s[2] = f[2];
    for (int i = 3; i <= N; i++)
        s[i] = s[i-1] + f[i];
    int n;
    while (scanf("%d", &n) == 1 && n) {
        printf("%lld\n", s[n]);
    }
    return 0;
}