一見すると $O(N^{2})$ かかるように思えるかもしれない。でも実は $O(N \log N)$ になる。

問題へのリンク

問題概要

$N$ 個の整数 $A_{1}, \dots, A_{N}$ が与えられる (それぞれ 0 または 1)。このとき、 $N$ 個の 0-1 変数 $x_{1}, \dots, x_{N}$ の値を、以下の条件を満たすように定めよ。

各 $i (=1, 2, \dots, N)$ に対して、 $x_{i} + x_{2i} + \dots$ を 2 で割ったあまりが $A_{i}$ に一致する

制約

$1 \le N \le 2 \times 10^{5}$

考えたこと

たとえば $N = 6$ のときはこんなふうになる。

$x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} \equiv A_{1} \pmod 2$
$x_{2} + x_{4} + x_{6} \equiv A_{2} \pmod 2$
$x_{3} + x_{6} \equiv A_{3} \pmod 2$
$x_{4} \equiv A_{4} \pmod 2$
$x_{5} \equiv A_{5} \pmod 2$
$x_{6} \equiv A_{6} \pmod 2$

これを見て思うことは、 $x_{6}, x_{5}, x_{4}, x_{3}, x_{2}, x_{1}$ の順に自動的に決まっていきそうだということ。まず $x_{4}, x_{5}, x_{6}$ が決まり、それが決まると

$x_{3} + x_{6} \equiv A_{3} \pmod 2$

より $x_{3}$ が決まり、

$x_{2} + x_{4} + x_{6} \equiv A_{2} \pmod 2$

より $x_{2}$ が決まり、

$x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} \equiv A_{1} \pmod 2$

より $x_{1}$ が決まる。これは一般にも成り立ちそうだ。

計算量解析

以上から一般に、 $x_{i+1}, x_{i+2}, \dots, x_{N}$ が決まっているときに

$x_{i} \equiv A_{i} - x_{2i} - x_{3i} - \dots$

とすればよいことがわかる。しかしこの解法は一見すると $O(N^{2})$ の計算量となりそうな気がしてしまう。

でもよくよく考えてみよう。 $x_{i}$ を求めるのに参照する $x_{j}$ の個数は $O(\frac{N}{i})$ となるのだ。そしてこれを $i = 1, 2, \dots, N$ について合計すると

$N + \frac{N}{2} + \frac{N}{3} + \dots + \frac{N}{N} = O(N \log N)$

となるのである。一般に

$1 + \frac{1}{2} + \frac{1}{3} + \dots$

を調和級数と呼び、 $O(\log N)$ 程度の発散スピードであることが知られている (証明は $y = \frac{1}{x}$ の積分が $\log{x}$ であることから来る)。

コード

実装上は $A_{i} - x_{2i} - x_{3i} - \dots$ のところは

$A_{i} + x_{2i} + x_{3i} + \dots$

に置き換えても OK。mod. 2 の世界では「引き算」も「足し算」も一緒だからだ。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N+1);
    for (int i = 1; i <= N; ++i) cin >> A[i];

    vector<int> x(N+1, 0);
    for (int i = N; i >= 1; --i) {
        int sum = A[i];
        for (int j = i*2; j <= N; j += i) sum += x[j];
        x[i] = sum % 2;
    }
    vector<int> res;
    for (int i = 1; i <= N; ++i) if (x[i] == 1) res.push_back(i);
    cout << res.size() << endl;
    for (auto v: res) cout << v << " ";
    cout << endl;
}