给定一个整数N（1<N<=4000000)的整数求∑GCD（i,j）i=1,2,3....j-1,2<=j<=n的值.参考了一下网上的题解，复述一下我理解后的思路，加深理解：
首先求出N以内的所有数的欧拉函数值phi[i],也就是比i小的与i互质的正整数的个数，比如a，b互质，那么最大公约数就是1，phi[b]值是m，表示与其互质的有m个，也就是这些数公因数之和为m；那么放大到k倍后，k*a和k*b的最大公约数就是k，那么相应的公约数之和变为k*m。数组a[i]就是表示k*b=i时增加的公约数之和的不断统计，a[2]+a[3]+...a[n]就是最后结果，代码把a[n]前面的累加到a[n],因此最终输出a[n]即可。
#include<stdio.h>
#define N 4000010
#define M 4000000 int phi[N];
typedef long long ll;
ll a[N]; void solve(void)
{
int i,j;
for(i=;i<=M;i++)
{
if(phi[i]==i)//phi[i]为i表示该数的欧拉函数值还没有求过，也就是该数为素数。
{
for(j=i;j<=M;j+=i)//筛法求欧拉函数值，
phi[j]=phi[j]/i*(i-);//phi[j]与素数i运算
}
for(j=;j*i<=M;j++)//经历上步之后phi[i]不会再改变了，此时phi[i]表示i的欧拉函数值，
a[j*i]+=j*phi[i];
}
for(i=;i<=M;i++)
a[i]+=a[i-];
} int main(void)
{
int n,i;
for(i=;i<=M;i++)
phi[i]=i;
solve();
while(scanf("%d",&n)&&n)
{
printf("%lld\n",a[n]);
}
return ;
}