求GCD(x,y)为素数个数也就是求d*gcd(x',y')个数,其中gcd(x',y')=1.d是质数.我们考虑枚举d.因为0<x,y<=N,那么x',y'<=N/d.
题目就变简单了,那么就是枚举每个质因子.然后用前缀统计下欧拉函数.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7+5;
ll prime[N],st[N],phi[N],cnt=0,sum[N];
void get_phi(int n)
{
    phi[1]=1;        
    for(int i=2;i<=n;i++)
    {
        if(!st[i])  {phi[i]=i-1; prime[cnt++]=i;}
        for(int j=0;prime[j]<=n/i;j++)
        {
            st[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
            {
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
    for(int i=2;i<=n;i++)   sum[i]=sum[i-1]+phi[i];
}

int main()
{
    ll n,ans=0;
    cin>>n;
    get_phi(n);
    for(int i=0;i<cnt;i++)
    {
        ans+=2*sum[n/prime[i]]+1;
    }
    cout<<ans<<endl;
    return 0;
}