给数n,求出所有gcd(i,j) (i<j<=n)的和.
对两个互质的数i,j,即gcd(i,j)=1,给它们都添加一个因子2,则有gcd(2i,2j)=2. 于是有gcd(ki,kj)=k.
求出所有互质的数对,然后就能进一步求出题目所需要的结果了.
用欧拉函数求出i以内与之互质的数的个数,并打表记录s=i*j内所有的数对i,j的gcd和:
sum[i*j]+=j*phi[i]
最后弄个前缀和,就能快速查询结果了.
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int phi[4000005];
long long sum[4000005];
void euler(int n){
for(int i=2;i<=n;++i) phi[i]=i;
for(int i=2;i<=n;++i){
if(phi[i]==i){
for(int j=i;j<=n;j+=i){
phi[j]=phi[j]/i*(i-1);
}
}
for(int j=1;i*j<=n;++j){
sum[j*i]+=j*phi[i];
}
}
for(int i=1;i<=n;++i){
sum[i]+=sum[i-1];
}
}
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n;
euler(4000000);
while(cin>>n&&n){
cout<<sum[n]<<endl;
}
return 0;
}