diverta 2019 Programming Contest-D "DivRem Number"

見落としがあって1回WAしました(というよりRE笑)が，特に苦戦せずACしました．

提出コード

考察

$N$ をお気に入りの数 $m$ で割ると商と余りが一致する(これを $a$ とします)ということを式で表すと

$N = am+a$

$a = \dfrac{N}{m+1}$

$a$ は当然自然数なので，上式が成り立つためには $m+1$ が $N$ の約数である必要があります．

ということで $N$ の約数を調べることから始め，(約数ｰ1)を足し込んでいく，という流れです．

ただし，約数ならなんでもいいというわけではなくて，約数のうちで上の式が成り立つようなものです．

約数列挙は $O(\sqrt{N})$ なので， $N=10^{12}$ でも間に合います．

約数の総和の公式あるじゃないですか．

計算量的にあれが使えるかなーって思ってそればっかり考えてたので，地味に時間かかりました．

約数の個数は $O(\sqrt{N})$ 個(ですよね...?)なので，普通に約数の個数分だけ足せば十分間に合いますね．