\(1 \leq i,j \leq N\) より、 \(i×j\) は \(N^2\) 以下です。

よって、 \(1^2,2^2, \ldots , N^2\) の約数の集合 \(d_1,d_2, \ldots ,d_N\) をそれぞれ高速に求めることが出来れば、 \(d_k\) の各要素 \(d_{k,1},d_{k,2},\ldots,d_{k,size(d_k)}\) について \(d_{k,l}\) と \(\frac{k^2}{d_{k,l}}\) が共に \(N\) 以下かどうか見ることによってこの問題を解くことが出来ます。

\( k^2 \) を素因数分解することを考えます。 \(k\) を素因数分解した結果が \(k=p^a×q^b×r^c× \ldots\) だとすると、 \(k^2\) の素因数分解の結果は \(k^2=p^{2a}×q^{2b}×r^{2c}× \ldots\) となります。よって、 \(k^2\) の素因数分解は \(k\) を素因数分解することによって \(O(\sqrt{k})\), もしくは適切な前計算のもと \(O(log \ k)\) で行うことが出来ます。

あとは、DFSなどを行えば \(k^2\) の素因数分解の結果から \(k^2\) の約数を全て列挙することが出来ます。( 各素因数の指数の値の組み合わせを\((2a+1)(2b+1)(2c+1)\ldots\) 通り全て試します )

よって、\(1^2,2^2, \ldots ,N^2\) の約数の個数の総和を \(S(N)\) として、\(O(N\sqrt{N}+S(N))\) もしくは \(O(Nlog N+S(N))\) でこの問題を解くことが出来ます。

\(S(N)\) の大きさですが、 \(N=200000\) で \(11859410\) なので十分間に合います。