记录编号	361150	评测结果	AAAAAAAAAA
题目名称	[UVa 11426] 最大公约数之和——极限版II	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.373 s
提交时间	2017-01-03 10:01:41	内存使用	100.43 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod=1e9+7,N=5e6+10;
ll n,ans,s[N],f[N];
int p[N],cnt;bool isp[N];
int main()
{
	freopen("gcd_extreme.in","r",stdin);
	freopen("gcd_extreme.out","w",stdout);
	f[1]=1;
	for (int i=2;i<N;i++){
		if (!isp[i]) p[++cnt]=i,f[i]=i-1;
		for (int j=1;j<=cnt&&i*p[j]<N;j++){
			int x=i*p[j];isp[x]=1;
			if (i%p[j]) f[x]=f[i]*f[p[j]];
				else{f[x]=f[i]*p[j];break;}
		}
	}
	for (int i=1;i<N;i++) s[i]=s[i-1]+f[i];
	while (1){
		scanf("%lld",&n);
		if (!n) break;
		ll ans=0;
		for (int l=1,r;l<=n;l=r+1){
			r=n/(n/l);
			ans+=(n/l)*(n/l)*(s[r]-s[l-1]);
		}
		ans=(ans-n*(n+1)/2)/2;
		printf("%lld\n",ans);
	}
	return 0;
}