https://atcoder.jp/contests/abc134/tasks/abc134_d
was difficult. Or rather, it was difficult to read the problem statement.
Question raised: Is $ O (\ sum (N / i)) $ in time?
In this problem, it is necessary to find $ N / i $ at any i. When considering this, it is good to perform integration. Since $ \ int (1 / N) = logN $, it can be suppressed by logN at worst.
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 = ' ')
Recommended Posts