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 math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n = i()
a = [0] + wi()
listb = []
zo = [0] * (n + 1)
re = 1
for i in range(n, 0, -1):
    re = 2
    s = 0
    while True:
        if i * re > n:
            re -= 1
            if (s + a[i]) % 2 == 1:
                listb.append(i)
                zo[i] = 1
            break
        else:
            s += zo[i * re]
            re += 1

print(len(listb))
for i in range(len(listb)):
    print(listb[-i-1])

Submission status: Accepted

Solution code:

N = int(input())

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

"""
for i in range(N):

    cnt = 1
    summ = 0
    flag = True

    while (i + 1) * cnt <= N:

        summ += a[(i + 1) * cnt -1]
        cnt += 1

    if summ % 2 != a[i]:
        flag = False
        print (i+1,"はみたさない")
        break

    else:
        pass
        print (summ,a[i],"でおｋ")

if flag :
    

    #print (lis)

    print (sum(a))

    ans = ""

    for i in range(len(a)):
        if a[i] == 1:
            ans += str(i+1) + " "

    print (ans[:-1])

else:
    print (-1)

"""

lis = [-1] * N



for i in range(N):

    i = N-i
    cnt = 2
    summ = 0
    flag = True

    while i * cnt <= N:

        summ += lis[i * cnt -1]
        cnt += 1

    #print (a[i-1],summ)

    if a[i-1] == 0 and summ % 2 == 0:
        lis[i-1] = 0
        #print ("a")

    elif a[i-1] == 0 and summ % 2 == 1:
        lis[i-1] = 1

    elif a[i-1] == 1 and summ % 2 == 0:
        lis[i-1] = 1

    elif a[i-1] == 1 and summ % 2 == 1:
        lis[i-1] = 0

    if not flag:
        break

if flag:

    #print (lis)

    print (sum(lis))

    ans = ""

    for i in range(len(lis)):
        if lis[i] == 1:
            ans += str(i+1) + " "

    print (ans)

else:
    print (-1)

Submission status: Accepted

Solution code:
N = int(input())
nums = input().split(" ")
a = [0]
for i in range(1, N+1):
    a.append(int(nums[i-1]))

b = [0 for i in range(N+1)]
multiple_list = [[] for i in range(N+1)]
for i in range(1,N+1):
    for j in range(i, N+1, i):
        multiple_list[j].append(i)

count = 0
for i in range(N, 0, -1):
    if a[i] == 1:
        b[i] = 1
        count+=1
        for num in multiple_list[i]:
            a[num] = 1 - a[num]

print(count)
for i in range(1,N+1):
    if b[i] == 1:
        print(i, end=" ")
if count != 0:
    print()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
s=sum(a)
ans=[0]*n
for i in range(n,0,-1):
    if i*2>n:
        ans[i-1]=a[i-1]
    else:
        j=i
        k=0
        while j<=n:
            k+=ans[j-1]
            j+=i
        if k%2!=a[i-1]:
            ans[i-1]=1
m=sum(ans)
print(m)
for i in range(n):
    if ans[i]==1:
        print(i+1,end=' ')

Submission status: Accepted

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

b = [0 for i in range(N)]

def check(i):
    cnt = 0
    n = i
    while n <= N:
        cnt += b[n-1]
        n += i
    return cnt

for i in range(N-1,-1,-1):
    if (a[i] + check(i+1))%2 == 1:
        b[i] = 1

ans = []
cnt = 0
for i in range(N):
    if b[i] == 1:
        cnt += 1
        ans.append(i+1)

print(cnt)
L = [str(int(i)) for i in ans]
print(' '.join(L))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]

n=I()
a=[0]+LI()
b=[0]*(n+1)
c=[0]*(n+1)
for i in range(n,0,-1):
    if c[i]!=a[i]:
        b[i]=1 #-b[i]
        c[i]=1-c[i]
        for j in range(2,int(i**0.5+1)):
            if i%j==0:
                c[j]=1-c[j]
                if j!=i//j: c[i//j]=1-c[i//j]
                #print('i=',i,'change',j,i//j)

s=sum(b)
if s%2!=a[1]:
    b[1]=1-b[1]
s=sum(b)    
print(s)

ans=[]
for i in range(1,n+1):
    if b[i]==1:
        #print(i,end=' ')
        ans.append(i)
if s!=0:
    print(*ans)

Submission status: Accepted

Solution code:
import math

def main():
    N = int(input())
    A = list(map(int, input().split()))
    b = [None]*N
    
    for i in range(N, math.ceil(N/2), -1):
        b[i-1] = A[i-1]
    
    for i in range(math.ceil(N/2), 0, -1):
        s = sum([b[j-1] for j in range(2*i, N+1, i)])
        b[i-1] = (A[i-1] + s) % 2
        
    b_out = [str(i+1) for i in range(N) if b[i] == 1]
    print(sum(b))
    print(' '.join(b_out))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]#amari
B = [0 for _ in range(N)]
s =  N//2

B[s:] = A[s:]

for i in reversed(range(s)):
  k = i+1
 # print(k)
#  print(A[i])
#  print(sum(B[i::k])%2)
  if A[i] == sum(B[i::k])%2:
    B[i] = 0
  else:
    B[i] = 1
#  print("-----")
  
print(B.count(1))
for i in range(len(B)):
  if B[i] == 1:
      print(i+1)

Submission status: Accepted

Solution code:
n = int(input())
boxes = [0] * n
amari = list(map(lambda x: int(x), input().split()))


# boxes の うち c の倍数の要素を足し合わせて2で割った余りを返す
def box_count(boxes, c):
    counter = 0
    for i in range(0, len(boxes), c):
        if i + c - 1 < len(boxes):
            counter += boxes[i + c - 1]
    return counter % 2
        

ballbox = ''   
# 後ろから決めていく
for i in range(n):
    if box_count(boxes, n - i) == 1:
        boxes[n - i - 1] = 1 - amari[n - i - 1]
    else:
        boxes[n - i - 1] = 0 + amari[n - i - 1]

    if boxes[n - i - 1] == 1:
        ballbox += str(n - i) + ' '

print(sum(boxes))
print(ballbox)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math

MOD = 2  # type: int

def solve(N: int, a: "List[int]"):
    b = [0] * N
    res = []
    balls = 0
    for i in range(N-1, -1, -1):
        k = i + 1
        c = 0
        for j in range(2, N // k + 1):
            c += b[j*k-1]
        b[i] = (a[i] + c) % 2
        if b[i]:
            res.append(str(k))
            balls += 1
    print(balls)
    if balls > 0:
        print(' '.join(res))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

n = int(input())
a = input().split()

#インデックスは1~n
oku = {}
okun = 0
for i in range(int(n/2)+1, n+1):
  oku[i] = int(a[i-1])
  if int(a[i-1]) == 1:
    okun += 1
    
for i in range(int(n/2), 0, -1):
  b = 0
  for j in range(i*2, n+1, i):
    if oku[j] == 1:
      b+=1
  if b % 2 == int(a[i-1]):
    oku[i] = 0
  else:
    oku[i] = 1
    okun += 1

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

Submission status: Accepted

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

ball_list = [0]*N

for i in range(N,0,-1):
  num_list = list(range(i,N+1,i))#-1で使う
  if num_list == []:
    ball_list[i-1] = a[i-1]
  else:
    sum_ = 0
    for j in num_list:
      sum_+=ball_list[j-1]
    if sum_%2 == a[i-1]:
      ball_list[i-1] = 0
    elif (sum_+1)%2 == a[i-1]:
      ball_list[i-1] = 1
    else:
      ball_list[i-1] = -1
if -1 not in ball_list:
  ball_sum = sum(ball_list)
  if ball_sum == 0:
    print(0)
  else:
    print(ball_sum)
    ans = [str(i+1) for i, x in enumerate(ball_list) if x == 1]
    print(' '.join(ans))
else:
  print('-1')

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)):
    if sum(b[i::i])%2 != a[i]:
        b[i] = 1

print(sum(b))
for i,j in enumerate(b):
    if j:
        print(i, end=" ")

Submission status: Accepted

Solution code:
import copy

N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)
B = copy.deepcopy(A)

if max(A) > 1:
	print("-1")
else:
	for i in range(N // 2, 0, -1):
		total = 0
		for j in range(2 * i, N + 1, i):
			total += B[j]
		if total % 2 != A[i]:
			B[i] = 1
		else:
			B[i] = 0
			
	print(sum(B))
	for i in range(len(B)):
		if B[i] == 1:
			print(i, end = " ")

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
A=deque(list(map(int,input().split())))
D={}
ans=[]
M=0
for i in range(N):
    a=A.pop()
    if N//(N-i)==1:
        D[N-i]=a
        if a==1:
            M+=1
            ans.append(str(N-i))
    else:
        p=N//(N-i)
        memo=0
        for j in range(1,p):
            memo+=D[(N-i)*(j+1)]
        if memo%2==a:
            D[N-i]=0
        else:
            D[N-i]=1
            M+=1
            ans.append(str(N-i))
print(M)
print(" ".join(ans))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[2]*n
for i in range(n,0,-1):
    if n//i==1:b[i-1]=a[i-1]
    else: b[i-1]=(sum(b[2*i-1::i])%2)^a[i-1]
print(sum(b))
for i in range(n):
    if b[i]==1:print(i+1,end=' ')

Submission status: Accepted

Solution code:
import sys, math

readline = sys.stdin.readline

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

F = [0] * N
div = 2
while True:
    if N // (div - 1) == 0:
        break

    for i in range(N // (div - 1) - 1, N // div - 1, -1):
        t = A[i]
        for j in range(i * 2 + 1, N, i + 1):
            t ^= F[j]
        F[i] = t
    div += 1

M = sum(F)
print(M)

s = [str(i + 1) for i, x in enumerate(F) if x == 1]
if len(s) > 0:
    print(' '.join(s))

Submission status: Accepted

Solution code:
len_arr = int(input())

conditions = [int(x) for x in input().split(' ')]
arr = [None] * len_arr

for i in reversed(range(0, len_arr)):
    sliced_arr = arr[i::i+1]
    current_condition = sum(sliced_arr[1:]) % 2

    if current_condition == conditions[i]:
        arr[i] = 0
    else:
        arr[i] = 1

# print(arr)
ball_indexes = [j+1 for j, ball in enumerate(arr) if ball == 1]

len_ans = len(ball_indexes)
print(len_ans)

if len_ans != 0:
    print(' '.join(map(str, ball_indexes)))

exit(0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 2  # type: int

def solve(N: int, A: "List[int]"):
    ans = set()
    for i in range(N,0,-1):
        c = 0
        for j in range(2,N + 1):
            if i * j <= N:
                if i*j in ans:
                    c += 1
            else:
                break

        if A[i-1] == 0:
            if c % 2 == 1:
                ans.add(i)
        else:
            if c % 2 == 0:
                ans.add(i)

    print(len(ans))
    if len(ans):
        print(" ".join([str(i) for i in ans]))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs,math
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))

n = onem()

a = l()
k = 0
for i in range(n):
	if a[-(i+1)] == 1:
		k = n - i
		break

m = [0 for i in range(k+1)]
al = 0
for i in range(k,0,-1):
	co = 0
	if k // i < 2:
		m[i] = a[i-1]
		al += a[i-1]
	else:
		if i != 1:
			for j in range(1,k // i):
				co += m[i * (j+1)]
				co %= 2
			m[i] = (co ^ a[i-1])
			al += m[i]
		else:
			al %= 2
			m[1] = (al ^ a[0])

print(sum(m))
kkkk = []

for i in range(len(m)):
	if m[i] == 1:
		kkkk.append(i)
if len(kkkk) != 0:
	print(jo(kkkk))

Submission status: Accepted

Solution code:


def submit():
    n = int(input())
    alist = [-1] + list(map(int, input().split()))

    i = n // 2
    while i > 0:
        j = i + i
        while j <= n:
            alist[i] += alist[j]
            j += i

        alist[i] %= 2
        i -= 1

    ans = alist[1:]

    print(sum(ans))
    for i, a in enumerate(ans):
        if a == 1:
            print(i + 1)

    return


if __name__ == '__main__':
    submit()

Submission status: Accepted

Solution code:
import sys
import copy


def input():
    return sys.stdin.readline()[:-1]


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    b = copy.copy(a)
    middle = len(a)//2-1
    ans = []

    for i in range(middle, -1, -1):
        s = 0
        b[i] = 0
        for j in range(i, n, i+1):
            s += b[j]
        b[i] = (s+a[i]) % 2

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = [0]*N

for i in range(N, 0, -1):
    if i > N // 2:
        b[i-1] = a[i-1]
    else:
        si = 0
        for j in range(i+i, N+1, i):
            si += b[j-1]
        if si % 2 == a[i-1]:
            b[i-1] = 0
        else:
            b[i-1] = 1

print(sum(b))
for i in range(N):
    if b[i] == 1:
        print(i+1 ,end=' ')

Submission status: Accepted

Solution code:
N = int(input())

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

b_list = [0]*(N//2)+a_list[N//2:]
for i, a in enumerate(range(N//2)):
    j = N//2 - i

    j_list = []
    k = j
    while(1):
        j = j + k
        if j > N:
            break
        else:
            j_list.append(j)
    #print(j_list)                                                                       
    s = 0
    for j in j_list:
        s += b_list[j-1]

    if s % 2 == a_list[k-1]:
        b_list[k-1] = 0
    else:
        b_list[k-1] = 1

print(len([str(i+1) for i, b in enumerate(b_list) if b == 1]))
print(' '.join([str(i+1) for i, b in enumerate(b_list) if b == 1]))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(range(n))
k = 2
s = 0
for i in range(n):
  if (n/2-1) < (n-i-1):
    b[n-i-1] = a[n-i-1]
  else:
    while n > k*(n-i)-1:
      s += b[k*(n-i)-1]
      k += 1
    if s % 2 == a[n-i-1]:
      b[n-i-1] = 0
    else:
      b[n-i-1] = 1
  k = 2
  s = 0
ans = b.count(1)
print(ans)
for i in range(n):
  if b[i] == 1:
    print(i+1, end=" ")

Submission status: Accepted

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
B_list = [0 for i in range(N)]
ans_list = ""

count = 0
for i in range(N-1, -1, -1):
    box_num = N // (i+1)
    sum_ball = 0
    for j in range(box_num):
        sum_ball += B_list[(j + 1) * (i + 1) - 1]
    if sum_ball % 2 != A_list[i]:
        B_list[i] = 1
        ans_list += str(i + 1) + " "
        count += 1

# print(A_list)
# print(B_list)

if count != 0:
    print(count)
    print(ans_list[:-1])
else:
    print(0)

Submission status: Accepted

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

for i in range(N-1,-1,-1):
    x = 2
    j = (i+1)*x-1
    while j <= N-1:
        A[i] = (A[i]-A[j])%2
        x += 1
        j = (i+1)*x-1
        

    if A[i] == 1:
        B.append(i+1)
        cnt +=1
B = [str(b) for b in B]

print(cnt)
if len(B) >= 1:
    print(' '.join(B))

Submission status: Accepted

Solution code:
def main():

    """ convenient functions
    # for i, a in enumerate(iterable)
    # q, mod = divmod(a, b)
    # divmod(x, y) returns the tuple (x//y, x%y)
    # Higher-order function: reduce(operator.mul, xyz_count, 1)
    # manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
    """

    """convenient decorator
    # @functools.lru_cache():
    # to facilitate use of recursive function
        # ex:
        # from functools import lru_cache
        # import sys
        # sys.setrecursionlimit(10**9)
        # @lru_cache(maxsize=None)
        # def fib(n):
        #     if n < 2:
        #         return n
        #     return fib(n-1) + fib(n-2)
        # print(fib(1000))
    """
    
    # import numpy as np
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product # https://docs.python.org/ja/3/library/itertools.html
    # accumulate() returns iterator! to get list: list(accumulate())
    from math import factorial, ceil, floor, sqrt
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  # prime factor
        b, e = 2, 0  # base, exponent
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        # TODO: How should I do when n - r is negative?
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
    from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
    import operator
    from operator import itemgetter
    # ex1: List.sort(key=itemgetter(1))
    # ex2: sorted(tuples, key=itemgetter(1,2))
    from functools import reduce, lru_cache
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)

    # first create factorial_list
    # fac_list = mod_factorial_list(n)
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
    def modinv(a, p = MOD):
        # evaluate reciprocal using Fermat's little theorem:
        # a**(p-1) is identical to 1 (mod p) when a and p is coprime
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        # fac_list = modfactorial_list(100)
        # print(modcomb(100, 5, modfactorial_list(100)))
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    """ initialize variables and set inputs
    # initialize variables
        # to initialize list, use [0] * n
        # to initialize two dimentional array, use [[0] * N for _ in range(N)]
    # set inputs
        # open(0).read() is a convenient method:
        # ex) n, m, *x = map(int, open(0).read().split())
        #     min(x[::2]) - max(x[1::2])
        # ex2) *x, = map(int, open(0).read().split())
        #     don't forget to add comma after *x if only one variable is used
    # preprocessing
        # transpose = [x for x in zip(*data)]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
        # flat = [flatten for inner in data for flatten in inner]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
    # calculate and output
        # output pattern
        # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
    """

    # functions used
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    R = lambda: list(map(int, r().split()))
    Rmap = lambda: map(int, r().split())
    Rfloat = lambda: list(map(float, r().split()))
    Rtuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    # single int: int(r())
    # single string: r()
    # single float: float(r())
    # line int: R()
    # line string: r().split()
    # line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
    # lines int: [R() for _ in range(n)]
    """

    if __name__ != '__main__':
        # for test
        sys.stdin = open('sample.txt')

    # ----------------------------------
    # main

    N = int(r())
    A = R()
    B = [0] * N
    for i in range(N-1, -1, -1):
        j = i + 1
        B[i] = (sum(B[i::j])%2 + A[i]) % 2
    print(sum(B))
    if sum(B) != 0:
        C = []
        for i, b in enumerate(B):
            if b == 1:
                C.append(i+1)
        print(*C)
    
    # end of main
    # ----------------------------------

    """memo: how to use defaultdict of list
    # initialize
    Dic = defaultdict(list)
    # append / extend
    Dic[x].append(y)
    # for
    for k, v in Dic.items():
    """

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N = _I()
A = LI()

'''
全箱にボールを入れてしまうと、2**N時間かかってしまうので無理
後ろから見たほうが絶対良い
最後の箱には、1であればボールが入るし、、0であればいれない
その次に、その数の約数を大きい方から確認していく
例えば、800が最後だとするとその次は400になる

'''


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)

    # divisors.sort()
    return divisors

ans = [None for _ in range(N)]
divisor_data = [None for _ in range(N)]
for n in reversed(range(0, N)):
    #  print('n', n)
    if divisor_data[n] == None:
        #  print('none')
        # 約数ではない数字
        if A[n] == 0:
            # ボールは入れない
            ans[n] = 0
        else:
            # ボール入れる
            ans[n] = 1
            divisors = sorted(make_divisors(n+1))
            #  print('divisors', divisors)
            for d in divisors[:-1]:
                if divisor_data[d-1] == None:
                    divisor_data[d-1] = 1
                else:
                    divisor_data[d-1] ^= 1
    else:
        #  print('yakusu')
        # 上の数字の約数
        if divisor_data[n] == A[n]:
            # ボールを入れない
            ans[n] = 0
        else:
            # 玉を追加
            ans[n] = 1
            divisors = sorted(make_divisors(n+1))
            #  print('divisors', divisors)
            for d in divisors[:-1]:
                if divisor_data[d-1] == None:
                    divisor_data[d-1] = 1
                else:
                    divisor_data[d-1] ^= 1
    #  print('div_data', divisor_data)

#  print('ans', ans)
#  print('div_data', divisor_data)
if all(a == 0 for a in ans):
    print(0)
else:
    print(ans.count(1))
    for aidx, a in enumerate(ans):
        if a == 1:
            print(aidx+1, end=' ')

Submission status: Accepted

Solution code:
import sys
N = int(input())
a = [int(x) for x in input().split()]
b = []
for i in reversed(range(int(N/2))):
    b = i
    stack = 0
    while b < N:
        stack += a[b]
        stack %= 2
        b += i+1
    a[i] = stack
c = sum(a)
if c == 0:
    print(c)
    sys.exit()
print(c)
for j in range(N):
    if a[j] == 1:
        print(j+1, end=" ")
print()

Submission status: Accepted

Solution code:
import sys
 
def main():
    input = sys.stdin.readline
    N = int(input())
    A = [0] + list(map(int, input().split()))
 
    M = 0
    ans = []
    B = [0] * (N+1)
    for i in range(N, 0, -1):
        cnt = 0
        for j in range(2*i, N+1, i):
            cnt += B[j]
 
        if A[i] != cnt % 2:
            B[i] += 1
            M += 1
            ans.append(i)
 
    if M == 0:
        print(0)
    else:
        ans = ans[::-1]
        print(M)
        print(' '.join(map(str, ans)))
 
 
if __name__ == '__main__':
    main()