思路

乍一看其实可以跟欧拉函数扯上关系。我们要求的是\(gcd(x,y) \in Prime, x, y \leq N\)的有序对个数。我们设那个质数为\(s\)，则可以化为：

\[ x = sa, y = sb \\ gcd(a, b) = 1 \]

嗯，看到欧拉函数的影子了。对于每一个质数\(s\)，它对答案的贡献是：

\[ 2 * \sum_{ 1 \leq i \leq \lfloor \frac{n}{s} \rfloor } \phi(i) – 1 \]

我来解释一下：因为\(x,y \leq n\)，所以\(sa \leq n\)，\(sb \leq n\)，得：

\[ a,b \leq \frac{n}{s} \]

所以会有这么多对，考虑这个是有序对，所以乘上二，再删除掉\((i,i)\)这样的有序对重复即可得到答案。注意，可以用前缀和欧拉函数值来进行优化。

代码

// BZ2818.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 10000005;
ll n, phi[MAX_N];
bool isPrime[MAX_N];
int main()
{
    //memset(isPrime, true, sizeof(isPrime));
    scanf("%lld", &n);
    for (int i = 2; i <= n; i++)
        phi[i] = i;
    for (int i = 2; i <= n; i++)
        if (!isPrime[i])
            for (int j = i; j <= n; j += i)
            {
                if (j != i)
                    isPrime[j] = true;
                phi[j] = phi[j] / i * (i - 1);
            }
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
        phi[i] += phi[i - 1];
    long long ans = 0;
    for (int i = 2; i <= n; i++)
        if (!isPrime[i])
            ans += 2 * phi[n / i] - 1;
    printf("%lld", ans);
    return 0;
}