记录编号	334195	评测结果	AAAAAAAAAA
题目名称	[UVa 11426] 最大公约数之和——极限版II	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	3.631 s
提交时间	2016-10-31 19:45:21	内存使用	100.64 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 5000005;
typedef long long ll;
ll read() {
	ll x=0; char ch;
	while(ch=getchar(),!isdigit(ch));
	x = ch-'0';
	while(ch=getchar(),isdigit(ch)) x = x*10+ch-'0';
	return x;
}
bool isnotprime[maxn]={1, 1};
int P, prime[maxn], phi[maxn], pw[maxn];
ll s[maxn];

void preprocess(int n) {
	s[1] = 1, pw[1] = 1;
	for(int i=2; i<=n; ++i) {
		if(!isnotprime[i]) {
			prime[++P] = i;
			s[i] = 2*i-1;
			pw[i] = i;
		}
		for(int j=1; j<=P && i*prime[j]<=n; ++j) {
			isnotprime[i*prime[j]] = 1;
 			if(i%prime[j]==0) {
				pw[i*prime[j]] = pw[i]*prime[j];
				s[i*prime[j]] = s[i]*prime[j]-(s[i/pw[i]]*pw[i])+s[i/pw[i]]*pw[i*prime[j]];
				break;
			} else {
				pw[i*prime[j]] = prime[j];
				s[i*prime[j]] = s[i]*(2*prime[j]-1);
			}
		}
	}
	// for(int i=1; i<=n; ++i) printf("%d %lld\n", i, s[i]);
	for(int i=1; i<=n; ++i) s[i] += s[i-1], s[i] -= i;
}

int N, q[50005];
int main(){
	freopen("gcd_extreme.in","r",stdin);
	freopen("gcd_extreme.out","w",stdout);
	N = 0;
	int size = 0;
	while(q[++N]=read())
		size = max(size, q[N]);
	preprocess(size+10);
	for(int i=1; i<N; ++i) 
		printf("%lld\n", s[q[i]]);
	getchar(), getchar();
	return 0;
}