思路

实际上就是求点$(x,y),\gcd(x,y)=1$，也就是这两个数互质的点的个数。

首先初始要加上$(0,1),(1,0),(1,1)$，然后可以发现这些点的分布是关于直线$x=y$对称的，我们只需要考虑$(x,y),x < y$的情况，将这个情况得到的数再乘上$2$再加上$3$即为结果。

看到互质就能够马上想到欧拉函数。我们将$y$从$2$开始枚举到$n$，求出$\phi(y)$再加起来，就是求上$\phi(y)$的总和：

$$ \sum_{i=2}^n{\phi(i)} $$

由于是多次查询，我们用前缀和来加速使之查询为$O(1)$。

关于线性筛法求欧拉函数

完整代码

#include <iostream>

using namespace std;

const int N = 1e3 + 10;

int primes[N], phi[N], s[N];
int cnt;
bool vis[N];

void init(){
    for (int i = 2; i < N; i ++ ){
        if (!vis[i])    primes[cnt ++ ] = i, phi[i] = i - 1;
        for (int j = 0; j < cnt and primes[j] <= N / i; j ++ ){
            vis[primes[j] * i] = 1;
            if (i % primes[j] == 0){
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
            else 
                phi[i * primes[j]] = phi[i] * (primes[j] - 1);
        }
    }

    for (int i = 2; i < N; i ++ )
        s[i] = s[i - 1] + phi[i];
}

int main(){
    init();

    int t;
    cin >> t;
    for (int i = 1; i <= t; i ++ ){
        int n;
        cin >> n;
        printf("%d %d %d\n", i, n, 3 + 2 * s[n]);
    }

    return 0;
}