ABC134-Dから学んだ計算量の求め方

問題

難しかった。というか問題文を読むことが難しかった。

今回の学び

1. 任意の整数＝全ての整数のようなニュアンス
2. 後ろから順に解いていくと一意に確定する
3. $O(\sum(N/i)) = O(NlogN)$

計算量の求め方

発生した疑問：$O(\sum(N/i))$って間に合うの？

今回の問題では任意のiにおいて$N/i$を求める必要がある。これを考えるとき、積分を行うと良い。$\int(1/N) = logN$であることから最悪でもlogNで押さえつけることができる。

まとめ

1. 数学的な文章になれる
2. 配列を前もしくは後ろから判定するのはよくあるし気づかなければいけない
3. 積分を考えると面積から計算時間を求めることができる。

コード

N = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)
b = [0] * N
M = 0
for i in range(N, 0, -1):
    ball = 0
    for j in range(i + i, N + 1, i):
        ball ^= b[j - 1]
    b[i - 1] = ball ^ a[i]
M = sum(b)
print(M)
for i in range(N):
    if b[i]:
        print(i + 1, end = ' ')