Odd Even Divisor

2 secs 1024 MB

解説

この問題はループを用いて愚直に約数の個数を数えることで $O(N^2)$ で解くことができます。

問題文でも言及されている通り、整数 $x$ $(1 ≦ x ≦ N)$ の正の約数 $d$ は $1 ≦ d ≦ x$ の範囲にのみ存在するため、この範囲を探索すれば十分です。実装の際は $x$ の偶奇による場合分けに注意してください。

なお、この問題は「正の約数の個数のテーブルを作る問題」に帰着されるため $O(N \mathrm{log} N)$ で解くこともできます（もっと高速に解く方法も存在します）。下記の問題も参考にしてください。