解説

想定解1 $O(N \log \log N)$

$N$ 以下の互いに素な自然数のペアの個数は、オイラーの $\phi$ 関数を使って $\sum_{i=1}^{N} \phi(i)$ と書くことができます。

$\phi(i) \quad (i = 1, 2, \ldots, N)$ は、エラトステネスの篩のようにすることで $O(N \log \log N)$ で求めることができます。

想定解2 $O(N \log N)$

前処理として、エラトステネスの篩を使って最小素因数のテーブルを $O(N \log \log N)$ で作成します。

$i = 1, 2, \ldots, N$ について、素因数分解しながら $\phi(i)$ を求めると、ひとつあたり $O(\log N)$ 、全体では $O(N \log N)$ で求めることができます。