この問題は、Nを素因数分解することで、O(N)で解くことができます。
Nにk種類の素因数があるとすると、素因数分解は以下のように表せます。
N=p1a1×p2a2×...×pkak
Nの約数は、k種類の素因数の中からそれぞれak個以下選んで作れるため、
Nの約数は(a1+1)(a2+1)...(ak+1)通りです。
N2の素因数分解は、Nの素因数分解を利用して以下のように表せます。
N2=p12a1×p22a2×...×pk2ak
よってN2の約数は(2a1+1)(2a2+1)...(2ak+1)通りであることがわかります。