题目传送

思路：

我们用f[n]表示gcd(1,n)+gcd(2,n)+gcd(3,n)+’…gcd(n-1,n),用s[n]表sum{f[i]|1<=i<=n} 则s[n]=s[n-1]+f[n];现在就是求f[n].因为 f[n]=gcd(1,n)+gcd(2,n)+gcd(3,n)+’…gcd(n-1,n),所有gcd(i,n)的值都是n的约数，可以按照约数值进行分类。例如gcd(i,n)=x,我们用g(n,x)表示和n的gcd为x的数有多少个，即满足条件的gcd(i,n)=x中的i有多少个，而满足gcd(i,n)=x的条件是gcd(i/x,n/x)=1,这就变成了g(n,x)表示gcd(i/x,n/x)=1总i/x有多少个，是不是很眼熟，就是求n/x的欧拉函数，所以g(n,x)=eluor(n/x);所以f[n]=sum{x*eluor[n/x]|x表示n的约数，eluor[n/x]表示共有多少个}

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=4e6;
int eluor[N+10],n;
ll f[N],s[N];
void init()
{memset(eluor,0,sizeof eluor);eluor[1]=1;//求欧拉函数for(int i=2;i<=N;i++)if(eluor[i]==0){for(int j=i;j<=N;j+=i){if(!eluor[j])eluor[j]=j;eluor[j]=eluor[j]/i*(i-1);}}for(int i=1;i<=N;i++)for(int j=i*2;j<=N;j+=i)f[j]+=(ll)i*eluor[j/i];//枚举i的倍数n,然后更新f[n];s[2]=f[2];//累加求和for(int i=3;i<=N;i++){s[i]=s[i-1]+f[i];}
}
int main()
{init();while(scanf("%d",&n)==1&&n){printf("%lld\n",s[n]);}return 0;
}