UVa11424 GCD

(这个题的预处理还是比较神奇的,我没想出来..)
显然这个题的特点是,n很小,组数却很大,我们想如何预处理.
首先理解题目在干吗,让我们求出(sum_{i = 1}^{n -1}sum_{j = i + 1}^{n}GCD(i,j))
套路的做
先算出
(GCD(i,j) == x)的数量
转而求
(GCD(i/x,j/x) == 1)
然后就到了预处理的阶段了
这个题的核心思想在于我们枚举每个因数对于不同n的贡献
枚举因子
(sum_{i=1}^{n}sum_{i+1}^{n}GCD(i,j) == x) 的贡献
(phi[n/x])
显然这样时间复杂度还是不过关的.((O(n^2)))我们考虑什么时候因子x会加贡献,当n为x的倍数的时候就又会产生贡献.
像这样预处理时间复杂度(O(log n))

for(int i = 1;i < maxN;++ i) {
		for(int j = i + i;j < maxN;j += i) {
			f[j] += i * phi[j / i];
		}
	}

然而我们求出的f数组是(sum_{1}^{n - 1} GCD(i,n))然后造一个前缀和就好了.
CODE:

#include <iostream>
#include <cstdio>
const int maxN = 200000 + 7;

int phi[maxN];
bool vis[maxN];
int prime[maxN];
int sum[maxN];
long long int f[maxN];

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

int main() {
	init();
	int fuck = 1;
	for(int i = 1;i < maxN;++ i) {
		for(int j = i + i;j < maxN;j += i) {
			f[j] += i * phi[j / i];
		}
	}
	for(int i = 1;i < maxN;++ i) {
		f[i] += f[i - 1];
	}
	while(fuck) {
		int n;
		scanf("%d",&n) ;
		if(!n) break;
		std::cout << f[n] << '
';
	} 
	return 0;
}