/*
给定n，对于所有的对（i,j）,i<j,求出sum{gcd(i,j)}
有递推式sum[n]=sum[n-1]+f[n]
其中f[n]=gcd(1,n)+gcd(2,n)+gcd(3,n)......
那么如何求出f[n],
设满足gcd(i,n)=x的组合有g(x,n)个,那么f[n]=sum{x*g(x,n)}
对于gcd(i,n)=x,即有gcd(i/x,n/x)=1,因为将n/x看做是固定的数，那么g(x,n)=phi[n/x]
求答案时直接先求出所有答案，因为枚举n的每个因子比较麻烦，所以直接枚举x即可，
那么由上述公式可推出==>f[x*t]+=x*phi[t]
筛出phi表
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 4000005
//#define ll long long
bool check[maxn+
10];
int phi[maxn+
10],prime[maxn+
10],tot;
void init(){
memset(check,0,
sizeof check);
phi[1]=
1;tot=
0;
for(
int i=
2;i<=maxn;i++
){
if(check[i]==
0){
prime[++tot]=
i;
phi[i]=i-
1;
}
for(
int j=
1;j<=tot;j++
){
if(i*prime[j]>maxn)
break;
check[i*prime[j]]=
1;
if(i%prime[j]==
0){
//prime[j]是i的因子
phi[i*prime[j]]=phi[i]*
prime[j];
break;
}
else
phi[i*prime[j]]=phi[i]*(prime[j]-
1);
}
}
}
long long f[maxn],s[maxn];
int main(){
init();
for(
int i=
1;i<=maxn;i++)
//枚举每个因数x
for(
int j=i+i;j<=maxn;j+=i)
//
f[j]+=(
long long)i*phi[j/
i];
for(
int i=
2;i<=maxn;i++
)
s[i]=s[i-
1]+
f[i];
int n;
while(cin>>
n,n)
cout<<s[n]<<
endl;
}
转载于:https://www.cnblogs.com/zsben991126/p/10430556.html
