Problem:


Score : 400 points

Problem Statement

There are N empty boxes arranged in a row from left to right.
The integer i is written on the i-th box from the left (1 \leq i \leq N).

For each of these boxes, Snuke can choose either to put a ball in it or to put nothing in it.

We say a set of choices to put a ball or not in the boxes is good when the following condition is satisfied:

For every integer i between 1 and N (inclusive), the total number of balls contained in the boxes with multiples of i written on them is congruent to a_i modulo 2.

Does there exist a good set of choices? If the answer is yes, find one good set of choices.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

a_i is 0 or 1.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

If a good set of choices does not exist, print -1.

If a good set of choices exists, print one such set of choices in the following format:

M
b_1 b_2 ... b_M

where M denotes the number of boxes that will contain a ball, and b_1,\ b_2,\ ...,\ b_M are the integers written on these boxes, in any order.

Sample Input 1

3
1 0 0

Sample Output 1

1
1

Consider putting a ball only in the box with 1 written on it.

There are three boxes with multiples of 1 written on them: the boxes with 1, 2, and 3. The total number of balls contained in these boxes is 1.

There is only one box with a multiple of 2 written on it: the box with 2. The total number of balls contained in these boxes is 0.

There is only one box with a multiple of 3 written on it: the box with 3. The total number of balls contained in these boxes is 0.

Thus, the condition is satisfied, so this set of choices is good.

Sample Input 2

5
0 0 0 0 0

Sample Output 2

0

Putting nothing in the boxes can be a good set of choices.



Sample input:
3
1 0 0


Sample output:
1
1

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
ans_list = np.zeros(N).astype(int)
N_2 = N // 2
ans = 0
for i in range(N):
    tmp = N - i - 1
    # print(tmp)
    if i < N_2:
        ans_list[tmp] = A[tmp]
        if A[tmp] == 1:
            ans += 1
    else:
        add = (np.sum(ans_list[tmp::(tmp + 1)]) + A[tmp]) % 2
        ans_list[tmp] = add
        if add == 1:
            ans += 1

print(ans)
for i in range(N):
    if ans_list[i] == 1:
        if i == N - 1:
            print(i + 1, end="")
        else:
            print(i + 1, end=" ")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

res = [0] * n
for i in range(n-1, -1, -1):
    res[i] = (a[i] + sum(res[2*i+1:n:i+1])) % 2

print(res.count(1))
for i in range(n):
    if res[i] == 1:
        print(i+1, end=' ')

Submission status: Accepted

Solution code:
n   = int(input())
li  = list(map(int,input().split()))
ans  = [0]*n
ans2 = 0
ans3 = []
mtp  = 0

for i in range(n,0,-1):
    tmp = 0
    if n//i == 1:
        ans[i-1] = li[i-1]
    else:
        mtp = n//i
        for j in range(1,mtp):
            tmp += ans[i*(j+1)-1]
        tmp %= 2

        ans[i-1] = (tmp^li[i-1])

for i in range(n):
    if ans[i]==1:
        ans2 += 1
        ans3.append(i+1)

print(ans2)
print(*ans3)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = set()
    # 逆順で考える
    # indexではなく数値で考える
    for i in reversed(range(1, n+1)):
        # 倍数計算は2倍したあとは数値的にnまでiごとにという形で算出
        for j in range(i*2, n+1, i):
            a[i-1] ^= a[j-1]
        if a[i-1] == 1:
            ans.add(i)
    print(len(ans))
    print(" ".join(map(str, ans)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

n = int(input())
a = [0]
a += list(map(int, input().split()))

b = [0]*(n+1)

for i in range(n,0,-1):
    sum = 0
    for j in range(2*i, n+1, i):
        sum ^= b[j]
    b[i] = sum^a[i]
    
ans = []
for i in range(1,n+1):
    if b[i]: ans.append(i)

print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

is_ball_contains = [0] * (n+1)
for i in range(n, 0, -1):
    if sum(is_ball_contains[i::i]) % 2 != a[i-1]:
        is_ball_contains[i] = 1

print(sum(is_ball_contains))
print(' '.join([str(i) for i, v in enumerate(is_ball_contains) if v]))

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = list(map(int, readline().split()))

B = [0] * (N + 1)
for i in range(N, 0, -1):
    j = i
    total = 0
    while j <= N:
        total += B[j]
        j += i
    if A[i - 1]:
        if total % 2 == 0:
            B[i] = 1
        else:
            B[i] = 0
    else:
        if total % 2 == 0:
            B[i] = 0
        else:
            B[i] = 1

print(sum(B))
for i in range(len(B)):
    if B[i] == 1:
        print(i)

Submission status: Accepted

Solution code:
n = int(input())
a = [0]+list(map(int,input().split()))
N = [i for i in range(1,n+1)]
N.reverse()
ans = [0]*(n+1)
b = []

for i in N:
  if i*2 > n:
    if a[i] == 1:
      ans[i] = 1
  else:
    if a[i] == 1:
      if sum(ans[i::i])%2 == 0:
        ans[i] = 1
    else:
      if sum(ans[i::i])%2 == 1:
        ans[i] = 1
        
for i in range(1,n+1):
  if ans[i] == 1:
    b.append(i)

print(len(b))
print(*b)

Submission status: Accepted

Solution code:
N = int(input())
a = [0] + list(map(int, input().split()))
b = [0] * (N+1)
M = 0
for i in range(N, 0, -1):
    temp_sum = sum([b[j] for j in range(i, N+1, i)]) - b[i]
    if temp_sum % 2 == 0 and a[i] == 0:
        b[i] = 0
    if temp_sum % 2 == 1 and a[i] == 0:
        b[i] = 1
        M += 1
    if temp_sum % 2 == 0 and a[i] == 1:
        b[i] = 1
        M += 1
    if temp_sum % 2 == 1 and a[i] == 1:
        b[i] = 0


print(M)
ans_list = [i for i in range(1, N+1) if not b[i] == 0]
print(*ans_list)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N = int(input())
    a = list(map(int, input().split()))
    b = [0] * N
    for i in range(N-1,-1,-1):
        if sum(b[i::i+1]) % 2 != a[i]:
            b[i] += 1
    print(b.count(1))
    for i in range(len(b)):
        if b[i] == 1:
            print(i+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [0] + list(map(int, input().split()))
B = [0] * (N + 1)

for i in reversed(range(1, N + 1)):
    bl = 0
    for j in range(i, N + 1, i):
        bl += B[j]
    if bl % 2 != A[i]:
        B[i] = 1

print(sum(B))
print(*[i for i, b in enumerate(B) if b == 1], sep=' ')

Submission status: Accepted

Solution code:
#d
n = int(input())
a = list(map(int, input().split()))
ans = [0]*len(a)
for i in range(len(a),0,-1):
    if sum(ans[i-1::i])%2 != a[i-1]:
        ans[i-1] = 1
print(sum(ans))
if sum(ans) > 0:
    ans_n = [str(i+1) for i, x in enumerate(ans)  if x==1]
    ans_n=" ".join(ans_n)
    print(ans_n)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
box = [0]*n
for i in range(n,0,-1):
  k = a[i-1]
  c = 0
  for j in range(1,n//i+1):
    c += box[i*j-1]
  if c%2 != k:
    box[i-1] = 1
ans = []
w = 0
for m in range(n):
  if box[m] == 1:
    w += 1
    ans.append(str(m+1))
print(w)
print(' '.join(ans))

Submission status: Accepted

Solution code:
N = int(input())
# A = list(map(int,input().split()))
A = [-1] + list(map(int,input().split()))
B = [0] * (N+1)
for i in range(N, 0, -1):
  tmp = 0
  for j in range(2*i, N+1, i):
    tmp += B[j]
  if tmp%2 != A[i]:
    B[i] = 1

print(B.count(1))
if B.count(1) > 0:
  print(" ".join(map(str, [ i for i,b in enumerate(B) if b==1 ])))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))

hako=[0]*n
for i in range(n):
    # print(n-i-1, sum(hako[n-i-1:n:n-i]))
    if (sum(hako[n-i-1:n:n-i])%2)!=a[n-i-1]:
        hako[n-i-1]+=1
# print(hako)

ans=[]
for i in range(n):
    if hako[i]==1:
        ans.append(str(i+1))

print(len(ans))
if len(ans)!=0:
    print(' '.join(ans))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = [0] + list(map(int, readline().split()))
    B = [0] * (N + 1)
    ans = []
    for i in range(N, 0, -1):
        x = sum(B[i::i])
        if x % 2 == A[i]:
            continue
        else:
            B[i] = 1
            ans.append(str(i))
    print(len(ans))
    print(' '.join(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, *a = map(int, open(0).read().split())
a = [0] + a
b = [0] * -~n
for i in range(n, 0, -1):
    s = sum(b[j] for j in range(i, n + 1, i))
    if s % 2 != a[i]:
        b[i] = 1
print(sum(b))
print(*[i for i, b in enumerate(b) if b == 1])

Submission status: Accepted

Solution code:
n = int(input())
alist = list(map(int, input().split()))
boxList = [0] * (n + 1)

m = 0
resultList = []

for i in range(1, n+1)[::-1]:
    sums = 0
    for j in range(1, n // i):
        sums += boxList[(j+1) * i]
    if sums % 2 != alist[i - 1]:
        boxList[i] = 1
        m+= 1
        resultList.append(i)

print(m)
if m != 0:
    print(' '.join(map(str, resultList)))

Submission status: Accepted

Solution code:
def divisor(n):
    # nの約数列挙
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass  # sortされていない


N = int(input())
*a, = map(int, input().split())
a = [0]+a
b = []
c = [0]*(N+1)

for i in range(N, 0, -1):
    if c[i] % 2 != a[i]:
        b.append(i)
        for d in divisor(i):
            if i % d == 0:
                c[d] += 1

print(len(b))
if len(b) > 0:
    print(*b)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
ans = []
for i in reversed(range(n)):
    if A[i]:
        ans.append(i+1)
        tmp = 1
        n = i+1
        while tmp*tmp <= n:
            if n%tmp == 0:
                A[tmp-1] ^= 1
                if tmp != n//tmp:
                    A[n//tmp-1]^=1
            tmp += 1
if len(ans) > 0:
    print(len(ans))
    print(*ans)
else:
    print(0)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

ans = [0] * n
for i in range(n - 1, -1, -1):
    sum = 0
    for j in range(i + i + 1, n, i + 1):
        sum += ans[j]

    ans[i] = a[i] - sum
    ans[i] %= 2

print(ans.count(1))

for i in range(n):
    if ans[i] == 1:
        print(i + 1, end=" ")

Submission status: Accepted

Solution code:
n = int(input())
a = [0] + list(map(int, input().split()))

for i in range(n, 0, -1):
    a[i] = sum(a[i::i]) % 2
print(sum(a))
for i in range(1, n + 1):
    if a[i] == 1:
        print(i)

Submission status: Accepted

Solution code:
def div(n):
    lower_div, upper_div = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_div.append(i)
            if i != n // i:
                upper_div.append(n // i)
        i += 1
    return lower_div + upper_div[::-1]

def main():
    n = int(input())
    A = list(map(int, input().split()))
    L = [0] * n
    b = []
    for i in reversed(range(n)):
        if A[i] != L[i] % 2:
            b.append(i+1)
            d = div(i + 1)
            for j in d:
                L[j-1] += 1
    print(len(b))
    print(*b)

main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    A = [0] + list(map(int, readline().split()))
    B = [0] * (N+1)
    ans = []
    for i in range(N,0,-1):
        x = sum(B[i::i])
        if x%2==A[i]:
            continue
        else:
            B[i] = 1
            ans.append(str(i))
    print(len(ans))
    print(' '.join(ans))




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortedresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortedresult:
        div.sort()
    return div
# endregion
N = ri()
a = ri_()
b = [0] * N
for i in reversed(range(N)):
    if (a[i] + sum(b[i::i+1])) % 2 == 1:
        b[i] = 1
M = sum(b)
print(M)
if M:
    for i in range(N):
        if b[i] == 1:
            print(i + 1, end = ' ')
    print('\n', end = '')

Submission status: Accepted

Solution code:
N = int(input())
A = [0] + list(map(int, input().split()))

B = [0] * (N + 1)

for i in range(N, 0, -1):
    # mod2 の足し算は xor
    sum_a = 0
    for j in range(i + i, N + 1, i):
        sum_a ^= B[j]
    B[i] = sum_a ^ A[i]

# print(A, B)
out = []
for i in range(1, N + 1):
    if B[i] == 1:
        out.append(i)
if len(out) > 0:
    print(len(out))
    print(*out)
else:
    print(0)

Submission status: Accepted

Solution code:
n = int(raw_input())
ais,res = [0] + map(int, raw_input().split()) ,[0 for _ in range(n +1)]
for u in range(n, 0, -1):
	c,cumul = u,0
	while(c <= n):
		cumul += res[c]
		c += u
	if ais[u] != (cumul % 2):  res[u] = 1
s = sum(res)
print s
if s: print ' '.join([str(i) for i in range(len(res)) if res[i] == 1])

Submission status: Accepted

Solution code:
import collections
import heapq
n = int(raw_input())
ais = [0] + map(int, raw_input().split()) 
#print ais
res = [0 for __ in range(n +1)]
for u in range(n, 0, -1):
	c = u*2
	cumul = 0
	while(c <= n):
		cumul += res[c]
		c += u
	if ais[u] != (cumul % 2): 
		res[u] = 1
s = sum(res)
print s
if s:
	print ' '.join([str(i) for i in range(len(res)) if res[i] == 1])

Submission status: Accepted

Solution code:
import collections
import heapq
n = int(raw_input())
ais = [0] + map(int, raw_input().split()) 
res = [0 for __ in range(n +1)]
used = set([])
for u in range(n, 0, -1):
	c = u*2
	cumul = 0
	for jj in range(u, n+1, u):
		cumul += res[jj]
	
	if ais[u] != (cumul % 2): 
		res[u] = 1
		used.add(u)
s = sum(res)
print s
if s:
	for x in used: print x,
	print

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
l = [0] * (n + 1)
ans = []
for i in range(n, 0, -1):
    cnt = 0
    for j in range(1, n // i + 1):
        cnt += l[i * j]
    if cnt % 2 != a[i - 1]:
        ans.append(i)
        l[i] = 1
print(len(ans))
print(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
n = int(input())
aa = tuple(map(int, input().split()))

balls = set()
for i in range(n, 0, -1):
    r = aa[i - 1]
    
    x = 0
    for j in range(i, n + 1, i):
        if j in balls:
            x += 1
    if x % 2 != r:
        balls.add(i)
print(len(balls))
if balls:
    print(' '.join(map(str, balls)))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    b = [0] * n
    for i in range(n):
        mod = n - i
        x = 1
        tmp = 0
        while x * mod <= n:
            tmp += b[x * mod - 1]
            x += 1
        if tmp % 2 != a[mod - 1]:
            b[mod - 1] = 1

    ans_m = 0
    ans_b = []
    for i in range(n):
        if b[i] > 0:
            ans_m += 1
            ans_b.append(i + 1)
    print(ans_m)
    if len(ans_b) > 0:
        print(*ans_b)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
def main():
    _ = int(input())
    A = list(map(int, input().split()))
    A.insert(0, 1e10)
    ans = []
    B = [0] * len(A)
    for i in range(len(A)-1, 0, -1):
        idx = i
        s = 0
        while idx <= len(A) - 1:
            s += B[idx]
            idx += i

        if s % 2 != A[i]:
            ans.append(i)
            B[i] = 1

    if len(ans) > 0:
        print(len(ans))
        print(*ans)
    else:
        print(0)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#coding: utf-8
N = int(input())
A = [0] + list(map(int, input().split()))
B = [0 for _ in range(N+1)]
ans = []
for i in range(N, 0, -1):
    v = 0
    j = i
    while j <= N:
        v += B[j]
        j += i
    if A[i] != v % 2:
        ans.append(i)
        B[i] = 1

ans.sort()
print(len(ans))
if len(ans) != 0:
    print(*ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.insert(0, 1e10)
    ans = []
    B = [0] * len(A)
    for i in range(len(A)-1, 0, -1):
        idx = i
        s = 0
        while idx <= len(A) - 1:
            s += B[idx]
            idx += i

        if s % 2 != A[i]:
            ans.append(i)
            B[i] = 1

    
    if len(ans) > 0:
        print(len(ans))
        print(*ans)
    else:
        print(0)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
arr = [False] * n

for i in range(n, 0, -1):
    if sum(arr[i - 1::i]) % 2 != a[i - 1]:
        arr[i - 1] = True

if not any(arr):
    print(0)
else:
    print(sum(arr))
    ans = []
    for i, x in enumerate(arr):
        if x:
            ans.append(i + 1)
    print(*ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
exist = [0]*(n+1)
ans = []
for i in range(n,0,-1):
    cnt = 0
    for j in range(1,n//i+1):
        cnt += exist[i*j]
    if (cnt%2) != A[i-1]:
        ans.append(i)
        exist[i] = 1
print(len(ans))
print(" ".join(map(str,ans)))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

ans = [0] * n

for i in reversed(range(1, n+1)):
    count = 0
    for j in range(2 * i, n + 1, i):
        count += ans[j-1]

    if count % 2 != a[i-1]:
        ans[i-1] = 1

print(sum(ans))
for i in range(n):
    if ans[i] == 1:
        print(i + 1)

Submission status: Accepted

Solution code:
N = int(input())
a = [0]
a += list(map(int, input().split(' ')))
b = [0 for _ in range(N + 10)]
for i in range(N, 0, -1):
  res = 0
  for j in range(N // i * i, i, -i):
    res = res ^ b[j]
  b[i] = res ^ a[i]
print(sum(b))
for i in range(1, N + 1):
  if b[i]:
    print(i)

Submission status: Accepted

Solution code:
def solve(N, As):
    boxes = [-1 for _ in range(N + 1)]
    for k in range(N, 0, -1):
        s = 0
        for i in range(k + k, N + 1, k):
            s += boxes[i]
        s %= 2

        if s == As[k - 1]:
            boxes[k] = 0
        else:
            boxes[k] = 1
    boxes = boxes[1:]
    # print(boxes)
    m = sum(boxes)
    ans = []
    for i, b in enumerate(boxes):
        if b == 1:
            ans.append(str(i + 1))
    return "\n".join([str(m), " ".join(ans)])


# print(solve(3, [1, 0, 0]))
# print(solve(5, [0, 0, 0, 0, 0]))
# print(solve(5, [0, 0, 0, 0, 1]))
# print(solve(5, [0, 0, 0, 1, 1]))
# print(solve(5, [0, 0, 1, 1, 1]))

# print(solve(4, [0, 0, 0, 0]))
# print(solve(4, [0, 0, 0, 1]))
# print(solve(4, [0, 0, 1, 1]))
# print(solve(4, [0, 1, 1, 1]))

if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split(" ")))
    print(solve(N, As))

Submission status: Accepted

Solution code:
n=int(input())

a = list(map(int,input().split()))

nice_box = [0]*n

for i in range(n-1,-1,-1):
  baisu = 2
  ball_memo = 0
  index = i+1
  while baisu * index - 1 < n:
    ball_memo += nice_box[baisu * index - 1]
    baisu += 1

  if ball_memo % 2 != a[i]:
    nice_box[i] += 1

ans = []

for i in range(n):
  if nice_box[i] == 1:
    ans.append(i+1)

print(len(ans))
if len(ans)>0:
  print(*ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
ball = [0]*(n) #入ってたら１

#ｎからn//2+1まで、Ａが１ならballも１
for i in reversed(range(n//2+1, n+1)):
    if A[i-1] == 1:
        ball[i-1] = 1

#n//2から１まで、その倍数をピックアップし、Ｂａｌｌを見る
for i in reversed(range(1, n//2+1)):
    s = n//i
    now = 0
    for j in range(2,s+1):
        if ball[i*j-1] == 1:
            now += 1
    if A[i-1] != now%2:
        ball[i-1] = 1

ans = []
for i in range(n):
    if ball[i] == 1:
        ans.append(i+1)
print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
m = 0
res = []
# 1 idx
for i in range(n, 0, -1):
    # i の倍数でbit立っているものの個数を数える
    cnt = 0
    idx = 2
    while i * idx <= n:
        if ans[i * idx - 1]:
            cnt += 1
        idx += 1
    debug = cnt
    if cnt % 2 != a[i - 1]:
        ans[i - 1] = 1
        m += 1
        res.append(i)
print(m)
if m:
    print(*res)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

ball = [0]*n

for i in reversed(range(1, n+1)):

    ball_in_or_not = a[i-1] ^ sum(ball[i-1:n:i]) % 2
    
    if ball_in_or_not == 1:
        ball[i-1] =1

if sum(ball) > 0:
    print(sum(ball))
    print(*[i+1 for i in range(n) if ball[i] > 0]) 

else:
    print(0)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

ball = [0]*n

for i in reversed(range(1, n+1)):

    a[i-1] ^= sum(ball[i-1:n:i]) % 2
    
    if a[i-1] == 1:
        ball[i-1] =1


if sum(ball) > 0:
    print(sum(ball))
    print(*[i+1 for i in range(n) if ball[i] > 0]) 

else:
    print(0)

Submission status: Accepted

Solution code:
n = int(input())
a = [0]+list(map(int,input().split()))
x = [0]*(n+1)
for i in range(n,0,-1):
    buf = 0
    for j in range(1,n//i+1):
        buf += x[i*j]
    if buf%2!=a[i]:x[i]=1
x = x[1:]
m = 0
b = []
for i in range(n):
    if x[i]==1:
        b.append(i+1)
        m+=1
print(m)
print(*b)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    a = [None] + list(map(int, input().split()))
    b = [None] + [0]*N
    for i in range(N, 0, -1):
        ball = [b[j] for j in range(i, N+1, i)]
        if sum(ball) % 2 != a[i]:
            b[i] = 1
    ans = [str(i) for i, n in enumerate(b) if n==1]
    print(len(ans))
    print(' '.join(map(str, ans)))
main()

Submission status: Accepted

Solution code:

N = int(input())
a = list(map(int, input().split()))

X = [0] * (N // 2) + a[N//2:]
#print(X)

for i in range(N//2):
    idx = -(i + N//2 + 1 + N % 2)
    step = N + idx + 1
    #print(idx, step)
    #print(X[idx:N+1:step])
    X[idx] = X[idx] if sum(X[idx:N+1:step]) % 2 == a[idx] else 1 - X[idx]

#print(X)

count = 0
s = ""
for i in range(N):
    if X[i] == 1:
        count += 1
        s += str(i+1) + " "

print(count)
print(s)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()

dic = DD(int)
ans = []

for i in range(N):
  n = N-i
  if dic[n]%2 != A[n-1]:
    for j in make_divisors(n):
      dic[j] += 1
    ans.append(n)

print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [0]+ list(map(int,input().split()))

for i in range(n,0,-1):
    a[i] = sum(a[i::i])%2
print(sum(a))
for i in range(1,n+1):
    if a[i] ==1:
        print(i)

Submission status: Accepted

Solution code:
N = int(input())

a_dic = list(map(int, input().split()))

ans = [-1 for i in range(N)]

for i in range(N):
    num = N-i
    index = 2
    cnt = 0
    while num * index <= N:
        if ans[num*index -1] != -1:
            cnt += ans[num*index -1]
        index += 1
    if cnt % 2 == 1:
        if a_dic[num-1] == 1:
            ans[num-1] = 0
        else:
            ans[num-1] = 1
    else:
        if a_dic[num-1] == 1:
            ans[num-1] = 1
        else:
            ans[num-1] = 0



print(sum(ans))
for i in range(N):
    if ans[i] == 1:
        print(i+1)

Submission status: Accepted

Solution code:
N = int(input())
a = [-1]+list(map(int,input().split()))
b = [0]*(N+1)
for i in range(N,0,-1):
    su = 0
    j = 2
    while i*j <= N:
        su += b[i*j]
        j+=1
    b[i] = (a[i]+su)%2

if sum(b)>0:
    print(sum(b))
else:
    print(0)
    exit()

ans =[]
for i in range(1,N+1,1):
    if b[i]==1:
        ans.append(i)
print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SI(): return input().split()

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from math import ceil, floor, log2
from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product


def solve():
    n = II()
    A = LI()
    box = [-1] * n
    ans = deque([])
    for i in range(n, 0, -1):
        sm = 0
        for j in range(i+i, n+1, i):
            # print(sm, box[j-1])
            sm ^= box[j-1]
        # print(A[i-1], sm)
        box[i-1] = A[i-1] ^ sm
        if box[i-1]:
            ans.appendleft(i)

    # print(box)
    print(sum(box))
    if sum(box):
        printlist(ans, ' ')

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
M = int(input())
B = [0] + list(map(int, input().split()))

ans = [0] * (M+1)
ret = []

for i in reversed(range(1, M+1)):
    if B[i] == sum(ans[i*2::i]) % 2:
        ans[i] = 0
    else:
        ans[i] = 1
    if ans[i] == 1:
        ret.append(i)

print(len(ret))
if len(ret) > 0:
    print(*ret[::-1])

Submission status: Accepted

Solution code:
M = int(input())
B = [0] + list(map(int, input().split()))

ans = [0] * (M+1)
ret = []

for i in reversed(range(1, M+1)):
    if i > M / 2:
        ans[i] = B[i]
    else:
        if B[i] == sum(ans[i*2::i]) % 2:
            ans[i] = 0
        else:
            ans[i] = 1
    if ans[i] == 1:
        ret.append(i)

print(len(ret))
if len(ret) > 0:
    print(*ret[::-1])

Submission status: Accepted

Solution code:
def solve():
    N, *a_l = map(int, open(0).read().split())
    a_l = [0] + a_l

    for i in range(N//2, 0, -1):
        a_l[i] = sum(a_l[i::i]) % 2

    b_l = [i for i, x in enumerate(a_l) if x]

    print(len(b_l))
    if len(b_l) != 0:
        print(' '.join(map(str, b_l)))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0] * N
ans = []

for i in range(N, 0, -1):
  cnt = sum(B[(i-1)::i])%2
  B[i-1] = A[i-1] ^ cnt
  if B[i-1]:
    ans.append(i)

print(sum(B))
print(*ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0] * N
ans = []

for i in range(N, 0, -1):
  j = 1
  cnt = 0

  while i * j <= N:
    cnt += B[(i*j) - 1]
    j += 1
  
  cnt %= 2
  B[i-1] = A[i-1] ^ cnt #排他的論理和XOR
  
  if B[i-1] == 1:
    ans.append(i)

print(sum(B))
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
a = list(input().split())

ball = []
for i in range(n, 0, -1):
    c = 2
    while i * c <= n:
        if a[i*c-1] == "1":
            a[i-1] = "1" if a[i-1] == "0" else "0"
        c += 1
    if a[i-1] == "1":
        ball.append(str(i))

print(len(ball))
if ball != []: print(" ".join(ball))