我们首先发现这样肯定是做不了的，所以我们枚举为\(gcd(x,y)=d\)的\(d\)

然后考虑以下的性质：

\(gcd(x,y)=1 \Leftrightarrow gcd(px,py)=p(p为素数)\)

这个很显然吧，因此当我们枚举素数\(d\)时只需要计算\(x,y\in[1,\lfloor\frac{n}{d}\rfloor]\)且\(gcd(x,y)=1\)的有序\(x,y\)对数即可。

我们假定\(x<=y\)，那么很容易结合欧拉函数的性质得出此时对答案的贡献为\(2\cdot\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\phi(i)-1\)

这个比较显然吧，假定\(i\in[1,\lfloor\frac{n}{d}\rfloor]\)为较大的那个，所以无序的对数就是\(\phi(i)\)，由于有序所以乘2。最后注意一下\((1,1)\)会被计算两次要减去。

最后给欧拉函数记一个前缀和即可。

CODE

#include<cstdio>

#define RI register int

using namespace std;

const int P=1e7;

int prime[P+5],phi[P+5],cnt,n; long long ans,sum[P+5]; bool vis[P+5];

inline void resolve(int x)

{

    vis[1]=phi[1]=1; sum[1]=2; for (RI i=2;i<=n;++i)

    {

        if (!vis[i]) prime[++cnt]=i,phi[i]=i-1;

        for (RI j=1;j<=cnt&&i*prime[j]<=n;++j)

        {

            vis[i*prime[j]]=1; if (i%prime[j]) phi[i*prime[j]]=phi[i]*(prime[j]-1);

            else { phi[i*prime[j]]=phi[i]*prime[j]; break; }

        }

        sum[i]=sum[i-1]+(phi[i]<<1);

    }

}

int main()

{

    RI i; scanf("%d",&n); for (resolve(n),i=1;i<=cnt;++i)

    ans+=sum[n/prime[i]]-1; return printf("%lld",ans),0;

}