求gcd(x,y)=p,p为质数的有序数对数，即求gcd(x/p,y/p)=1，即在n/p范围内互质的有序数对数；

枚举每个质数p，设a=x/p,b=y/p且a,b<n/p;

我们钦定a=k,则a=k时的贡献为φ(k)，所以a取遍所有值，贡献就是∑φ(i) 1<=i<=n/k；

因为是有序数对数，所以答案乘2；然后要减1，因为重复计算了1,1，即a=1,b=1和b=1,a=1;

#include<cstdio>
#include<iostream>
#include<cmath>
#define R register int 
#define ll long long
using namespace std;
const int N=10000010;
int n,cnt,pri[N],phi[N];
ll po[N],sum[N],ans;
bool v[N];
inline void PHI() { v[1]=true; phi[1]=1;
    for(R i=2;i<=n;++i) {
        if(!v[i]) pri[++cnt]=i,phi[i]=i-1;
        for(R j=1;j<=cnt&&i*pri[j]<=n;++j) {
            v[i*pri[j]]=true; if(i%pri[j]==0) {
                phi[i*pri[j]]=phi[i]*pri[j]; break;
            } phi[i*pri[j]]=phi[i]*phi[pri[j]];
        }
    }
}
signed main() { 
    scanf("%d",&n); PHI();
    for(R i=1;i<=n;++i) sum[i]=sum[i-1]+phi[i];
    for(R i=1;i<=cnt;++i) {
        ans+=2*sum[n/pri[i]]-1;
    } printf("%lld\n",ans); //while(1);
}

---

2019.5.14