發現對于gcd問題要多和歐拉函數聯系在一起，雖然有時候并不是互質，但是我們知道有多少互質的然后根據互質的數目就能解決很多個gcd的問題
對于這道題目，題目要求的是所有數對的gcd的和，直接思考的話有難度。但是我們如果聯想到歐拉函數問題就解決了許多。
我們對于每個數都考慮他的歐拉函數值，即有phi[x]個數和x互質，設gcd(x,i)=1,那么gcd(tx,ti)=t，因為我們考慮的是所有互質的數，所以可以證明每對數都會被訪問一次且只會訪問一次。
所以我們要做的就是得到歐拉函數值，然后對于每個數字x,和tx的最大公約數為t的數目肯定也只有phi[x]個，那么關于x的所有的gcd和就是(1+2+…+t)*phi[i]，求和就可以了
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<ctime>
#include<climits>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=4e6+5;int n;
int phi[MAXN];
int prime[MAXN];
bool check[MAXN];
int tot;void creat_phi()
{tot=0;phi[1]=1;for(int i=2;i<MAXN;i++){if(!check[i]){phi[i]=i-1;prime[tot++]=i;}for(int j=0;j<tot && prime[j]*i<MAXN;j++){check[i*prime[j]]=true;if(i%prime[j]){phi[i*prime[j]]=(prime[j]-1)*phi[i];}else{phi[i*prime[j]]=prime[j]*phi[i];break;}}}
}int main()
{creat_phi();ll ans,t;while(~scanf("%d",&n) && n){ans=0;for(int i=2;i<=n;i++){t=n/i;ans+=t*(t+1)/2*phi[i];}printf("%lld\n",ans);}return 0;
}
