この問題は、NNを素因数分解することで、O(N)O(\sqrt N)で解くことができます。

NNkk種類の素因数があるとすると、素因数分解は以下のように表せます。

N=p1a1×p2a2×...×pkakN={p_1}^{a_1}×{p_2}^{a_2}×...×{p_k}^{a_k}

NNの約数は、kk種類の素因数の中からそれぞれaka_k個以下選んで作れるため、
NNの約数は(a1+1)(a2+1)...(ak+1)(a_1+1)(a_2+1)...(a_k+1)通りです。

N2N^2の素因数分解は、NNの素因数分解を利用して以下のように表せます。

N2=p12a1×p22a2×...×pk2akN^2={p_1}^{2a_1}×{p_2}^{2a_2}×...×{p_k}^{2a_k}

よってN2N^2の約数は(2a1+1)(2a2+1)...(2ak+1)(2a_1+1)(2a_2+1)...(2a_k+1)通りであることがわかります。