记录编号	85768	评测结果	AAAAAAAAAA
题目名称	[UVa 11426] 最大公约数之和——极限版II	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	24.433 s
提交时间	2014-01-11 13:45:28	内存使用	76.61 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<iomanip>
using namespace std;
typedef long long ll;
const int SIZEN=4000000;
int phi[SIZEN+10]={0};
void phi_table(int n){
	int i,j;
	phi[1]=1;
	for(i=2;i<=n;i++){
		if(!phi[i]){
			for(j=i;j<=n;j+=i){
				if(!phi[j]) phi[j]=j;
				phi[j]=phi[j]/i*(i-1);
			}
		}
	}
}
ll s[SIZEN+10]={0},f[SIZEN+10]={0};
void prepare(void){
	int i,j;
	for(i=1;i<=SIZEN;i++) for(j=i*2;j<=SIZEN;j+=i) f[j]+=i*phi[j/i];
	s[2]=f[2];
	for(j=3;j<=SIZEN;j++) s[j]=s[j-1]+f[j];
}
int main(){
	freopen("gcd_extreme.in","r",stdin);
	freopen("gcd_extreme.out","w",stdout);
	phi_table(SIZEN);
	prepare();
	while(true){
		int n;
		scanf("%d",&n);
		if(!n) break;
		printf("%lld\n",s[n]);
	}
	return 0;
}