暴力枚举

$O(n^2logn)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1010;

int divier[N][N];
int cnt[N];

int n, c;

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}

void init(){
    for(int i = 1; i < N; i++){
        for(int j = 1; j < N; j++){
            if(gcd(i, j) == 1){
                divier[i][cnt[i]++] = j;
                }
            }
        }
}

int main(){
    scanf("%d", &c);
    int t = 1;
    init(); //O(n^2 * logn)
    while(c--){ //O(c * n)
        scanf("%d", &n);
        int ans = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < cnt[i]; j++){
                if(divier[i][j] <= n) ans++;
                }
            }
        printf("%d %d %d\n", t++, n, ans + 2);  //+2是考虑(0,y) 和 (x, 0) 这两种情况
        }
    return 0;
}