正の整数 NNN の約数の個数を kkk として iii 番目の約数を did_idi とおきます.ある約数 did_idi に対して dj=N/did_j = N / d_idj=N/di もまた NNN の約数となることを利用すると(NNN が平方数の場合は di=djd_i = d_jdi=dj)
と表せます (NNN が平方数の場合にも成立) .
よって,問題は「NNN の約数の総和は NNN の倍数であるか」と言い換えられ,これは試し割り法によって時間計算量 O(N)O(\sqrt{N})O(N) で約数列挙すれば解くことができます.
倍積完全数