https://atcoder.jp/contests/abc134/tasks/abc134_d
a été difficile. Ou plutôt, il était difficile de lire l'énoncé du problème.
Question posée: Est-ce que $ O (\ sum (N / i)) $ est dans le temps?
Dans ce problème, il est nécessaire de trouver $ N / i $ à n'importe quel i. En considérant cela, il est bon d'effectuer l'intégration. Puisque $ \ int (1 / N) = logN $, il peut être supprimé par logN au pire.
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