可以转化成求n以内gcd为1的，gcd为2的………gcd为n-1的i，j（i＜j≤n）的对数，然后对数乘以相应的gcd即可
然后gcd为k的i，j的对数为m=n/k以内的i，j互质的对数，即2以内与2互质的数的数目+3以内与3互质的数的数目+……+m以内与m互质的数的数目
即欧拉函数值之和
要注意的是 i 要小于 j ，即 i！=j ，所以要先令phi【1】=0再求和
#include <iostream> #include <stdio.h> #include <math.h> #include <string.h> #include <vector> #include <algorithm> #include <map> using namespace std; typedef long long LL; const LL MAXN=4e6+3; #define fi first #define se second LL phi[MAXN]; LL prime[MAXN]; LL total; bool isprime[MAXN]; void make() { LL m=MAXN-3; memset(isprime,true,sizeof(isprime)); isprime[1]=isprime[0]=false; total=0; phi[1]=1; for(int i=2;i<=MAXN;i++) { if(isprime[i])prime[++total]=i,phi[i]=i-1; for(int j=1;j<=total&&i*prime[j]<=m;j++) { isprime[prime[j]*i]=false; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } else phi[i*prime[j]]=phi[i]*(prime[j]-1); } } } LL n; int main() { make(); phi[1]=0; for(int i=2;i<=4000000;i++)phi[i]+=phi[i-1]; while(scanf("%lld",&n)!=-1&&n) { LL ans=0; for(int i=1;i<=n;i++) { LL z=n/i; if(z>1)ans+=phi[z]*i; } printf("%lld\n",ans); } }