题意：
给一个数 N ，求 N 范围内所有任意两个数的最大公约数的和。
思路：
f 数组存的是第 n 项的 1~n-1 与 n 的gcd的和，sum数组存的是 f 数组的前缀和。
sum[n]=f[1]+f[2]+f[3]+…+f[n]
sum[n-1]=f[1]+f[2]+…+f[n-1]
sum[n]=sum[n-1]+f[n]
所以我们求出f[n]的值即可
1~n-1与 n 的最大公约数暴力来求肯定超时；
设gcd(x,n)=i 表示 n 和 x 的最大公约数为i，那么gcd( x/i , n/i )=1
即转化为 求n/i 的欧拉函数值。a[ n / i ]
比如:
a [ 6 / 1 ] = a[ 6 ] = 2
a[ 6 / 2 ] = a[ 3 ] = 2
a[ 6 / 3 ] = a[ 2 ] = 1
a[ 6 / 4 ] = a[ 1 ] = 1
a[ 6 / 5 ] = a[ 1 ] = 1
a [ j / i ] * i =2 * 1+2 * 2 + 1 * 3
for(int i=1;i<N;i++)//计算1~N的所有数
for(int j=i*2;j<N;j=j+i)// [1,n-1] 与n的gcd 的和
//j必须是i的整数倍 ，因为下面要计算 j/i
f[j]+=a[j/i]*i;
欧拉函数数组 a[ n ] 装的是 n 以内与 n互质的数。
欧拉函数表：
a[1]=1;
for(int i=2;i<N;i++)//欧拉函数表
{
if(!a[i])//素数筛的基础，i 进去的是素数
for(int j=i;j<N;j=j+i)
{
if(!a[j]) a[j]=j;
a[j]=a[j]/i*(i-1);//欧拉公式 φ（n）=n * (1 - 1/p1) * （1 - 1/p2）* .....
}
}
完整代码：
#include<string.h>
#include<stdio.h>
#define N 4000010
typedef long long ll;
ll f[N+5],ans[N+5],a[N+5];
void yao()
{
for(int i=0;i<=N;i++)
f[i]=0,ans[i]=0,a[i]=0;
a[1]=1;
for(int i=2;i<N;i++)//欧拉打表
{
if(!a[i])
for(int j=i;j<N;j=j+i)
{
if(!a[j]) a[j]=j;
a[j]=a[j]/i*(i-1);
}
}
for(int i=1;i<N;i++)
for(int j=i*2;j<N;j=j+i)//[1,n-1] 与n的gcd 的和
f[j]+=a[j/i]*i;
// f[6]=a[6/1==1]*1 + a[6/2==3]*2 + a[6/3==2]*3
////// for(int i=1;i<=6;i++)
////// printf("%d ",a[i]);
////// printf("\n");
for(int i=2;i<=N;i++)
ans[i]=ans[i-1]+f[i];
}
int main()
{
int n;
yao();
while(~scanf("%d",&n)&&n)
printf("%lld\n",ans[n]);
return 0;
}
/*
f[6]
1,6 5,6 1=a[6]
2,6 4,6 2=a[3]
3,6 1=a[2]
*/