记录编号	309727	评测结果	AAAAAAAAAA
题目名称	[UVa 11426] 最大公约数之和——极限版II	最终得分	100
用户昵称	Hzoi_chairman	是否通过	通过
代码语言	C++	运行时间	25.928 s
提交时间	2016-09-20 15:37:37	内存使用	88.75 MiB

/*
  Name: 最大公约数之和――极限版II
  Copyright: 
  Author: chairman
  Date: 20/09/16 15:31
  Description: 数论题
  			   用g(n,i)表示满足gcd(x,n)=i且x<n的个数,则f[n]=sum{i*g(n,i)}
			   gcd(x,n)=i则gcd(x/i,n/i)=1,由此满足条件的x/i有phi(n/i)个,即g(n,i)=phi(n/i)
			   如果枚举n的约数会很慢,可以枚举每一个i的倍数 
*/
#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 4000100
#define ll long long
int read()
{
	int x,f=1;
	char ch;
	while(ch=getchar(),!isdigit(ch))if(ch=='-')f=-1;
	x=ch-48;
	while(ch=getchar(),isdigit(ch))x=x*10+ch-48;
	return x*f;
}
void write(ll x)
{
	if(x<0)putchar('-'),x=-x;
	int cnt=0;char ch[50];
	while(ch[++cnt]=x%10+48,x/=10);
	while(putchar(ch[cnt]),--cnt);
	putchar('\n');
}
bool check[maxn];
int phi[maxn],prime[maxn],nn[maxn],n;ll f[maxn],s[maxn];
void get_phi()
{
	phi[1]=1;int cnt=0;
	for(int i=2;i<=n;i++)
	{
		if(!check[i])
		{
			prime[++cnt]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=cnt;j++)
		{
			if(i*prime[j]>n)break;
			check[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=phi[i]*prime[j];break;
			}
			else phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
}
int main()
{
	freopen("gcd_extreme.in","r",stdin);
	freopen("gcd_extreme.out","w",stdout);
	int tot=0;
	while(nn[++tot]=read(),n=max(n,nn[tot]),nn[tot]);
	tot--;
	get_phi();
	for(int i=1;i<=n;i++)
		for(int j=i*2;j<=n;j+=i)//注意每次加i,因为要保证是i的倍数 
			f[j]+=i*phi[j/i];//注意是加等于,以为j会有多个因数 
	s[2]=f[2];
	for(int i=3;i<=n;i++)s[i]=s[i-1]+f[i];
	for(int i=1;i<=tot;i++)write(s[nn[i]]);
	//system("pause");
}