实际上，这个问题，除了 $(1,0), (0, 1), (1, 1)$
这三个点之外，$(x, y)$ 满足条件，当且仅当
$1 \leqslant x,y \leqslant N, x \neq y$ 并且 $\text{gcd}(x, y)=1$

根据对称性，实际上，对于 $2 \leqslant y \leqslant N$
找到对应的 $1 \leqslant x < y$ 并且 $\text{gcd}(x, y)=1$
这样的 $\phi (y)$ 就是答案

$\textbf{ans} = 3 + 2\cdot \sum_{i = 2}^{N} \phi(i)$

Eratosthenes筛求Euler函数
一开始用 $\phi(i) = i$ 表示 $i$ 是一个质数
然后更新 $j = [i, 2i, 3i, \cdots, N]$， $i$ 作为一个素因子
$\phi(j) = \phi(j) * \frac{i-1}{i}$

const int maxn = 1000 + 10;
int phi[maxn];
int N;

void euler(int N) {
    _rep(i, 2, N) phi[i] = i;
    _rep(i, 2, N) {
        if(phi[i] == i) {
            for(int j = i; j <= N; j += i) phi[j] = phi[j] / i * (i-1);
        }
    }
}

void init() {
    memset(phi, 0, sizeof(phi));
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    cin >> kase;

    int T = 0;
    while (kase--) {
        init();
        scanf("%d", &N);

        // then solve
        euler(N);
        int sum = 0;
        _rep(i, 2, N) sum += phi[i];
        sum *= 2, sum += 3;

        printf("%d %d %d\n", ++T, N, sum);
    }
}

线性筛法递推求Euler函数

线性筛法的思路是，每个合数仅仅被最小质因子 $p$ 筛一次
用 $fl[\cdots]$ 标记最小质因子

$\forall i, fl[i] = 0, i$ 为素数，储存到 $\to prime$
$\forall i = [2, N]$ , 为当前的 $i$
乘上一个当前已得到的素因子 $\forall x \in prime$

$$i \times x \xrightarrow{fl[…]} \begin{cases} fl[i] \\\ x \end{cases} $$

更新 $fl[i \cdot x]$，即 $i \cdot x$ 的最小素因子
它要么是 $fl[i]$，要么是 $x$
$\textbf{if } fl[i] < x$ 当前素因子就已经被找到了，不检查其他 $prime$
$\textbf{else }, fl[i \cdot x] = x$

那么Euler其实就是在上述算法的基础上
每一次标记最小素因子，并且只在第一次标记的时候，记录

$$ \phi(i \cdot p) = \begin{cases} \phi(i) \cdot p && p \mid i \\\ \phi(i) \cdot (p-1) && p \nmid i \end{cases} $$

const int maxn = 1000 + 10;
int phi[maxn], fl[maxn];
int N;

void euler(int N, vector<int>& prime) {
    memset(fl, 0, sizeof(fl));
    prime.clear();

    _rep(i, 2, N) {
        if(fl[i] == 0) {
            fl[i] = i, prime.push_back(i);
            phi[i] = i - 1;
        }
        for(const auto& x : prime) {
            if(fl[i] < x || i * x > N) break;
            fl[i*x] = x;
            phi[i*x] = phi[i] * (i % x ? x - 1 : x);
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    cin >> kase;
    int T = 0;
    while (kase--) {
        scanf("%d", &N);
        vector<int> prime;
        euler(N, prime);

        int sum = 0;
        _rep(i, 2, N) sum += phi[i];
        sum *= 2, sum += 3;

        printf("%d %d %d\n", ++T, N, sum);
    }
}