[AtCoder] ABC 134 D – Preparing Boxes

問題

方針

最後の箱から調べる

後ろの箱からボールを入れることを考えると、その箱以降の倍数の個数は変化しないことが分かります。

例えば、\( i < \dfrac{N}{2} \) を満たす \( i \) の倍数は、\( 2i < N \) より、ただ一つの箱が存在することが分かります。ここで、\( i = \dfrac{N}{2} \) の箱を考えると、\( i \) の倍数は、\( i \) と \( 2i \) の箱を考えれば良いことが分かります。

イメージとしては後ろからエラトステネスの篩をやる感じです。

コード