D - Preparing Boxes

・問題URL

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

・思考

・当たり前だが、入れる/入れないのbit全探索は無理。
・N番目の箱に入れるかは決まってる。
・となると、N-1、N-2...みたいに大きい順から決まっていきそうだけど、例えば8、4、2みたいな共通する約数を持つ箱はどうしよう

・キーワード

・調和級数

・解法

・大きい箱から決めていく。まず箱Nが決まる。N-1以降で箱iに入れるかは、箱2i,3i,...(Nまで)に入っている個数の和をO(N/i)で計算して、aとの偶奇が同じなら入れない。異なるなら入れる。
・となると、O(N²)に見えるが、1/1+1/2+1/3+...はlogNで上からおさえられることが知られており、O(NlogN)である。

・コード

int main() {

   ll N;
   cin >> N;
   vector<ll>A(N + 1), B(N + 1);
   rep(i, N)cin >> A[i+1];
   B[N] = A[N];
   for (int i = N - 1; i >= 1; i--) {
       ll count = 0;
       for (int j = i * 2; j <= N; j += i) {
           if (B[j] == 1)count++;
       }
       if ((count % 2) != A[i])B[i]++;
   }

   set<ll>s; 
   ll M=0;
   for (int i = 1; i <= N; i++) {
       if (B[i] == 1) {
           s.insert(i);
           M++;
       }
   }
   cout << M << endl;
   for (auto v : s)cout << v << " ";
}