想定解

正の整数 NN の約数の個数を kk として ii 番目の約数を did_i とおきます.ある約数 did_i に対して dj=N/did_j = N / d_i もまた NN の約数となることを利用すると(NN が平方数の場合は di=djd_i = d_j

  • 1/d1++1/dk=(d1++dk)/N1/d_1 + \cdots + 1/d_k = (d_1 + \cdots + d_k) / N

と表せます (NN が平方数の場合にも成立) .

よって,問題は「NN の約数の総和は NN の倍数であるか」と言い換えられ,これは試し割り法によって時間計算量 O(N)O(\sqrt{N}) で約数列挙すれば解くことができます.

参考

倍積完全数