AtCoder Beginner Contest 134：D - Preparing Boxes

問題
解法
解答

問題

https://atcoder.jp/contests/abc134/tasks/abc134_d

解法

i = N, (N - 1), (N - 2), ... の倍数の順番に考えていく．そうすると i 番目の箱にボールを入れるかどうか決める際 i * 2, i * 3, ... 番目の箱にボールを入れるかどうかは既に決まっているので，これらの箱に入れたボールの総数の偶奇と a_i が異なる場合のみ i 番目の箱にボールを入れればよいとなる．全体で計算量は O(N / 1 + N / 2 + N / 3 + ... + N / N) となり O(NlogN) となる．これは N / x を 1 ~ N で x について定積分すると NlogN となるから（らしい）．