Preparing Boxes [AtCoder Beginner Contest 134 D]

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

解説

https://atcoder.jp/contests/abc134/submissions/6478841

B[i] := i番目の箱にボールが何個入っているかと定義しておこう。
まず、自明なところから考えていこう。
A[N]=B[N]
これがまず分かるところ。
この事実から考えると、後ろから考えていくのがよさそう。
あるB[i]の値を決定するには、B[i2], B[i3], ... の値とA[i]から決定ができそうだが、
ちょうど後ろから決めることでBの値はすべてわかるので、other=B[i2]+B[i3]+...を計算すると、
other%2==A[i]であれば、パリティは変えたくないのでB[i]=0、違うならB[i]=1とする。
こう考えていくと、-1になる場合はないので、どんどん作っていこう。
あとは、B[i]=1になっているiを集めて答える。

int N, A[201010], B[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 1, N + 1) cin >> A[i];

    rrep(i, N, 1) {
        int other = 0;
        for (int x = i * 2; x <= N; x += i) if (B[x]) other++;
        if (other % 2 != A[i]) B[i] = 1;
    }

    vector<int> ans;
    rep(i, 1, N + 1) if (B[i]) ans.push_back(i);

    int M = ans.size();
    printf("%d\n", M);
    rep(i, 0, M) {
        if(i) printf(" ");
        printf("%d", ans[i]);
    }
    printf("\n");
}