记录编号	223578	评测结果	AAAAAAAAAA
题目名称	[UVa 11426] 最大公约数之和——极限版II	最终得分	100
用户昵称	夜雨	是否通过	通过
代码语言	C++	运行时间	3.152 s
提交时间	2016-02-11 21:46:56	内存使用	80.42 MiB

#include <iostream>
#include <cstdio>
#include <cstring>

#define N 4000010
#define LL long long

using namespace std; 

LL f[N], phi[N];
int prime[N], tot, n;
bool v[N];

/*
f(n) = sum{ d * phi(n/d) ,d|n}
f(pn) = (phi(p)+p) * f(n)
f(p^k) = k * (p-1) * p^(k-1)
*/

int logn(int &a,int b){	//ans = logb(a)
	int ans=0;
	while(a%b==0) a/=b,ans++;
	return ans;
}

int gcd(int a,int b){
	if(!a) return b;
	if(!b) return a;
	return gcd(b,a%b);
}

int calc(int n){
	int ans=0;
	for(int i=1;i<=n;i++) 
		if(n%i==0) ans+=i*phi[n/i];
	int pos=0;
	for(int i=1;i<=n;i++) pos+=gcd(i,n);
	if(pos!=ans) puts("error");
	return ans;
}

LL F(int x,int k){
	int tmp=1,n=1;
	LL ans=0;
	for(int i=1;i<=k;i++) n*=x;
	for(int i=0;i<=k;i++){
		ans+=tmp*phi[n/tmp];
		tmp*=x;
	}
	if(ans!= k*phi[n] + n) puts("error");
	return ans;
}

void prepare(){
	f[1]=phi[1]=1;
	tot=0;
	for (int i=2;i<N;i++){
		if(!v[i]){
			prime[++tot]=i;
			phi[i]=i-1;
			f[i]=phi[i]+i;
		}
		for(int j=1;j<=tot&&i*prime[j]<N;j++){
			if(i*(LL)prime[j]>=(LL)N) break;
			int p=i*prime[j];
			v[p]=true;
			if(i%prime[j]==0){
				phi[p]=phi[i]*prime[j];
				int tmp=p;
				int k=logn(tmp,prime[j]);
				f[p]=f[tmp] * (k*phi[p/tmp] + p/tmp);
				break;
			}
			else{
				phi[p]=phi[i]*phi[prime[j]];
				f[p]=f[prime[j]]*f[i];
			}
		}
	}
}

int main(){
	freopen("gcd_extreme.in","r",stdin);
	freopen("gcd_extreme.out","w",stdout);
	prepare();
	f[0]=0;
	for(int i=1;i<N;i++) f[i]=f[i]-i+f[i-1];
	while(scanf("%d",&n),n!=0){
		cout<<f[n]<<endl;
	}
	return 0;
}