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:
N = int(input())
l = list(map(int, input().split()))
a = [0] * (N+1)
for k in reversed(range(1, N+1)):
    num = sum([a[k*i] for i in range(1, N//k+1)])
    if num % 2 != l[k-1]:
        a[k] = 1
M = sum(a)
ans = [i for i in range(1, N+1) if a[i] > 0]
 
print(M)
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [0] + list(map(int, input().split()))
    B = [0] * (N + 1)
    ans = []
    for i in range(N,0,-1):
        B[i] = A[i]
        j = 2
        while i * j < (N + 1):
            B[i] ^= B[i * j]
            j += 1
        
        if B[i] % 2 == 1:
            ans.append(i)

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





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    N = int(input())
    a = [0] + list(map(int, input().split()))

    box = [0] * (N+1)
    for i in range(N, 0, -1):
        tmp = sum(box[i::i])
        if tmp%2 == a[i]:
            continue
        else:
            box[i] = 1
    ans = []
    for i in range(1, N+1):
        if box[i] == 1:
            ans.append(i)
    print(sum(box))
    if len(ans) != 0:
        print(*ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

hako = [0]*N
last_ans = 1

for i in range(N-1, -1, -1):
    #print(i)
    check = 0
    kijun = i+1
    baisuu = 1
    total = 0
    while kijun*baisuu <= N:
        if hako[kijun*baisuu-1] == 1:
            total += 1
        baisuu += 1
    total %= 2
    if total != a[i]:
        hako[i] = 1

if last_ans == 1:
    print(hako.count(1))
    if hako.count(1) != 0:
        buf = [i+1 for i, x in enumerate(hako) if x == 1]
        print(' '.join(map(str, buf)))
else:
    print(-1)

Submission status: Accepted

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

print(sum(b))
for k in range(N):
    if b[k]==1:
        if k<N-1:
            print(k+1,end=" ")
        else:
            print(k+1)

Submission status: Accepted

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

for i in range(1,n+1)[::-1]:
    sum_i = sum(b[(i-1)::i])
    if sum_i%2 != a[i-1]:
        ans.append(i)
        b[i-1] = 1

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = [0] + list(map(int,read().split()))

for n in range(N//2,0,-1):
    A[n] = sum(A[n::n])&1

I = [i for i, x in enumerate(A) if x]

print(len(I))
if len(I) > 0:
    print(' '.join(map(str,I)))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i, ai in reversed(list(enumerate(a, 1))):
    s = sum(ans[j - 1] for j in range(i + i, n + 1, i))
    ans[i - 1] = (s + a[i - 1]) % 2
ans = list(map(lambda x: x[0], filter(lambda x: x[1] == 1, enumerate(ans, 1))))
print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    A = [int(i) for i in readline().split()]

    ans = []
    B = [0] * N
    for i in reversed(range(N)):
        s = sum(B[i::i+1])
        if s % 2 == A[i]:
            continue
        else:
            B[i] += 1
            ans.append(i+1)
    
    print(sum(B))

    if len(ans):
        print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
# import bisect
# import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = na()

    b = [0 for i in range(n)]
    ans = []

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

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

    tmp = len(ans)
    print(tmp)
    if tmp > 0:
        print(*ans, sep=" ")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

m = 0
ans = [0]*N
for i in range(N, 0, -1):
    a = A[i-1]
    cnt = 0
    for k in range(i+i, N+1, i):
        cnt += ans[k-1]
    if a != cnt % 2:
        ans[i-1] = 1
        m += 1

print(m)
for i in range(N):
    if ans[i] > 0:
        print(i+1, end=' ')
print()

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
ans = [0 for i in range(N)]
ans2 = []
for i in range(N):
    p = N - 1 - i
    if a[p] != sum(ans[p::p + 1]) % 2:
        ans[p] = 1
        ans2.append(str(p + 1))
print(sum(ans))
print(" ".join(ans2))

Submission status: Accepted

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

for i in range(n-1, -1, -1):
    ms = sum(box[i::i+1])
    if ms % 2 != a[i]:
        box[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
# 非破壊的に逆順で返す
for i in reversed(range(1, N+1)):
    v = A[i-1]
    # range(start, stop, step)
    for j in range(i, N+1, i):
        v += ans[j-1]
    # 箱に入れるかを決める
    ans[i-1] = v % 2

M = sum(ans)
print(M)
if M:
    # もし入っていれば、その添字に１を足して入れる。それをanpac
    print(*(i+1 for i, b in enumerate(ans) if b == 1))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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))
del a[0]
for i,v in enumerate(a):
    if v==1:
        print(i+1,end=" ")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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))
del a[0]
for i,v in enumerate(a):
    if v==1:
        print(i+1,end=" ")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N = int(input())
A = list(map(int,input().split()))

B = [0]*(N+1)
Ans = []

for k in range(N,0,-1):
    cnt = 0
    for i in range(k,N+1,k):
        cnt += B[i]
    cnt %= 2
    if A[k-1] != cnt:
        B[k] = 1
        Ans.append(k)

print(len(Ans))
if Ans:
    print(*Ans)

Submission status: Accepted

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

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

ans = []
for i in range(1,n+1):
  if ball[i] == 1:
    ans += [str(i)]
    
if ans:
  print(len(ans))
  print(" ".join(ans))
else:
  print(0)

Submission status: Accepted

Solution code:
n = int(input())
a= list(map(int, input().split()))
s = [0]*n
ans2 = []
for i in range(1, n+1):
  temp = sum(s[n-i::n+1-i])
  if (temp % 2 == 0 and a[-i] == 1) or (temp % 2 == 1 and a[-i] == 0) :
    s[-i] = 1
    ans2.append(str(n+1-i)) 

ans2.reverse()
print(sum(s))
print(" ".join(ans2))

Submission status: Accepted

Solution code:
n = int(input())
a_ls = list(map(int, input().split()))
a_ls = [0] + a_ls
box_ls = [0] * (n+1)
root = n ** 0.5
for i in range(n,0,-1):
    if 2*i > n:
        box_ls[i] = a_ls[i]
    else:
        Sum = 0
        num = i + i
        # ここの条件式不安あり
        while num <= n:
            Sum += box_ls[num]
            num += i
        rest = Sum % 2
        if (rest == 1 and a_ls[i] == 1) or (rest == 0 and a_ls[i] == 0):
            box_ls[i] = 0
        else:
            box_ls[i] = 1
ans_ls = []
for box_name, ball_num in enumerate(box_ls[1:],1):
    if ball_num == 1:
        ans_ls.append(str(box_name))
M = len(ans_ls)
print(M)
if M > 0:
    print(' '.join(ans_ls))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
box = [0]*n
ans = []
cnt = 0
for i in reversed(range(1, n+1)):
    tmp = 0
    for j in range(i*2, n+1, i):
        tmp ^= box[j-1]
    if a[i-1] != tmp:
        ans.append(i)
        box[i-1] = 1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    N=int(input())
    A=[0]+list(map(int,input().split()))
    ans=[0]*(N+1)
    s=[0]*(N+1)

    for i in reversed(range(1,N+1)):
        cnt=0
        for j in range(i+i,N+1,i):
            cnt^=s[j]
        if (A[i]==1 and cnt!=1) or (A[i]==0 and cnt!=0): s[i]=1
    
    print(sum(s))
    for i in range(1,N + 1):
        if s[i]==1:
            print(i)






    

resolve()

Submission status: Accepted

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

r = [0] * (N//2)
Nn =  N//2
r.extend(A[Nn:])

for i in range(Nn):
    n = Nn - i - 1
    s = 0
    for j in range(N//(n+1)):
        if r[(n+1)*(j+1) -1] == 1:
            s += 1
    s += A[n]
    s %= 2
    r[n] = s

x = ''
y = 0
k = 0
for num, i in enumerate(r):
    if i == 1:
        k = 1
        x += str(num+1) + ' '
        y += 1

print(y)
if k:
    print(x)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

N = getN()
A = [-1] + getList()
lista = [0 for i in range(N + 1)]

# 逆順に実施する
# 1からループ回さないと34行目でバグる
for i in range(1, N + 1)[::-1]:
    cnt = 0
    # 2 * i, 3 * i...について
    for j in range(2 * i, N + 1, i):
        cnt += lista[j]
    # もしcnt % 2とa[i]が合わなければb[i]にボールを置いて修正
    if cnt % 2 != A[i]:
        lista[i] = 1
ans = []
for i in range(N + 1):
    if lista[i] == 1:
        ans.append(str(i))
print(len(ans))
print(" ".join(ans))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N = int(input())
a = list(map(int,input().split()))
ans = [0]*(N)
for i in range(N//2+1,N+1):
    ans[i-1] = a[i-1]
for i in range(1,N//2+1):
    j = N//2 +1-i
    s = 0
    for k in range(2*j,N+1,j):
        s += ans[k-1]
    s = s % 2
    ans[j-1] = (s - a[j-1])%2
ans2 = []
for i in range(N):
    if ans[i] == 1:
        ans2.append(i+1)
print(len(ans2))
print(*ans2)

Submission status: Accepted

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

ans = []

for i in range(n):
    j = n-i
    count = 0
    itr = 2
    while(1) :
        s =j * itr
        if s > n :
            break
        count += ans[n-1-(s-1)]
        itr +=1
    j = n -i
    if (count%2 == a[j-1]):
        ans.append(0)
    else:
        ans.append(1)

ans.reverse()
print(sum(ans))
for i,j in enumerate(ans):
    if j == 1:
        print(i+1, end=" ")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


mod = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))
box = [0] * (N+1)
ans = []
for i in reversed(range(1, N+1)):
    # iの倍数の箱の合計
    if sum(box[i::i]) % 2 != A[i-1]:
        # sum_ = sum([box[i*j] for j in range(1, N//i+1)])
        box[i] = 1
        ans.append(i)
print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
ans = [0] * N
for i in range(N):
    tmp = N - i
    kosuu = N // tmp
    if kosuu == 1:
        if a[tmp-1] == 1:
            ans[tmp-1] = 1
    else:
        sub_sum = 0
        for j in range(kosuu-1):
            sub_sum += ans[tmp * (j + 2) -1]
        if a[tmp-1] != sub_sum % 2:
            ans[tmp-1] = 1
            
true_ans = []
for i in range(N):
    if ans[i] == 1:
        true_ans.append(i + 1)
print(sum(ans))
print(*true_ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: 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 printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

def solve():
    n = II()
    A = LI()

    B = [-1] * n
    for i in range(n, 0, -1):
        # print(i)
        s = 0
        for j in range(i+i, n+1, i):
            # print(f' {j}')
            s ^= B[j-1]
        B[i-1] = A[i-1] ^ s
    # print(B)

    print(sum(B))
    for idx, b in enumerate(B):
        if b: print(idx+1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

def md(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
b = [0]*n
ans = []
for i in range(n-1,-1,-1):
    if (b[i]%2 != a[i]):
        c = md(i+1)
        ans.append(i+1)
        for j in c:
            b[j-1] += 1
if (b[0]%2!=a[0]):
    print(-1)
else:
    print(len(ans))
    print(*ans)

Submission status: Accepted

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

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

ans = []
for i,b in enumerate(B):
    if b == 1:
        ans.append(i+1)
print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
# ARC 134
N = int(input())
a_list = list(map(int, input().split()))
b_list = [0] * N

res_set = set([])
for i in list(range(N))[::-1]:
    if a_list[i] != sum(b_list[i::i+1])%2:
        res_set.add(i+1)
        b_list[i] = 1

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

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
alis = li()

blis = [0]*n
for i in reversed(range(1,n+1)):
    sums = 0
    for k in range(1,n+1):
        if k*i > n:
            break
        sums += blis[k*i - 1]
    if (sums % 2) != alis[i-1]:
        blis[i-1] = 1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
arr=[2]+limii()
cnt=0
ans=[]
mat=[0]*(n+1)
for i in range(1,n+1)[::-1]:
    temp=0
    for j in range(2*i,n+1,i):
        temp+=mat[j]
    
    if temp%2!=arr[i]:
        mat[i]=1

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

print(cnt)
print(*ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
p = [] 
s = [0 for i in range(n)]
for i in range(n):
    q = 0
    k = n-i
    for j in range(2,n+1):
        if k*j <= n:
            q = (q+s[k*j-1])%2
        else:
            break
    if (a[k-1]+q)%2 == 1:
        s[k-1] = 1
        p.append(k)
print(len(p))
for i in range(len(p)):
    print(p[i],end=' ')

Submission status: Accepted

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

for i in range(1, N//2 + 1)[::-1]:
    wa = 0
    for j in range(2, N+1):
        if i * j > N:
            break
        wa += A[i*j]
    wa %= 2
    if A[i] == wa:
        A[i] = 0
    else:
        A[i] = 1


A = A[1:]
print(A.count(1))
for i, j in enumerate(A):
    if j == 1:
        print(i+1, end=' ')

Submission status: Accepted

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

ans = []
box = [0] * (n+1)
for i in range(n, 0, -1):
    num = i
    sum_num = 0
    while num <= n:
        sum_num += box[num]
        num += i
    if a[i] != sum_num%2:
        ans.append(i)
        box[i] = 1

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

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict

geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

N = gete(int)
a = geta(int)

b = [-1 if 2 * i <= N else a[i - 1] for i in range(N + 1)]

i = N + 1
while i > 1:
    i -= 1
    if b[i] != -1:
        continue

    if sum([b[j] for j in range(i * 2, N + 1, i)]) & 1 == a[i - 1]:
        b[i] = 0
    else:
        b[i] = 1

bm = list(filter(lambda i: b[i] == 1, range(1, N + 1)))

print(len(bm))
if len(bm) > 0:
    print(*bm, sep=" ")

Submission status: Accepted

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

ans=[]
for i in range(n-1,-1,-1):
    if i+1>n//2:
        L[i]=a[i]
    else:
        t=n//(i+1)
        el=0
        for j in range(2,t+1):
            el += L[(i+1)*j-1]
        L[i]=(el+a[i])%2
    if L[i]==1:
        ans.append(str(i+1))

print(len(ans))
if len(ans)>0:
    print(' '.join(ans))

Submission status: Accepted

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

for i in range(N-1,-1,-1):
  summ = sum(b[2*i+1::i+1])
  if summ%2==0:
    b[i] = a[i]
  else:
    b[i] = 1-a[i]
  #print(i,summ,b[i])
    
ans=[]
print(sum(b))
for i,num in enumerate(b):
  if num==1:
    ans.append(i+1)

print(*ans)

Submission status: Accepted

Solution code:
# D - Preparing Boxes

N = int(input())
A = [int(a) for a in input().split()]

ans = [0] * N
for i in reversed(range(1, N + 1)):
    x = 0
    for j in range(i, N + 1, i):
        x += ans[j - 1]
    if x % 2 != A[i - 1]:
        ans[i - 1] = 1

print(ans.count(1))
print(*[i for i in range(1, N + 1) if ans[i - 1] == 1])

Submission status: Accepted

Solution code:
N = int(input())
*A, = map(int, input().split())
b = [0] * N
for i in range(N-1, -1, -1):
   chk = sum(b[i:N:i+1])
   if chk % 2 ^ A[i]:
       b[i] = 1

print(sum(b))
ans = []
for i, v in enumerate(b):
    if v == 1:
        ans.append(i+1)
print(*ans)

Submission status: Accepted

Solution code:
N = int(input())
*A, = map(int, input().split())
b = [0] * N
for i in range(N-1, -1, -1):
   chk = sum(b[i:N:i+1])
   if chk % 2 ^ A[i]:
       b[i] = 1

print(sum(b))
ans = []
for i, v in enumerate(b):
    if v == 1:
        ans.append(i+1)
print(*ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [-1] + [int(_) for _ in input().split()]
    haco = [0] * (N+1)
    m = 0

    for i in range(1, N+1)[::-1]:
        max_j = N // i
        cc = 0
        for j in range(1, max_j+1):
            cc += haco[i*j]
        cc -= haco[i]
        cc %= 2
        if cc == A[i]: haco[i] = 0
        else:
            haco[i] = 1
            m += 1
    print(m)
    if m:
        for i in range(1, N+1):
            if haco[i]: print(i, end=' ')
        print('')
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
input=sys.stdin.readline

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

b=[0]*n

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


print(sum(b))
print(" ".join([str(k+1)  for k,v in enumerate(b)  if v== 1]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
input=sys.stdin.readline

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

b=[0]*n

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


print(sum(b))
print(" ".join([str(k+1)  for k,v in enumerate(b)  if v== 1]))

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))

ans = [i for i, v in enumerate(A) if v]
print(*ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = [int(e) for e in input().split()]

    B = [0] * n
    for i in range(n, 0, -1):
        s = 0
        for j in range(n // i):
            s += B[i * (j + 1) - 1]

        if s % 2 != A[i - 1]:
            B[i - 1] = 1

    print(B.count(1))

    if B.count(1) != 0:
        print(' '.join([str(i + 1) for i in range(n) if B[i] == 1]))


if __name__ == '__main__':
    main()

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))
ans = [i for i, v in enumerate(A) if v]
print(*[i for i, v in enumerate(A) if v])

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
res = [0] * N
for i in range(N, 0, -1):
    tmp = 0
    for j in range(i * (N // i), i, -i):
        tmp += res[j - 1]
    if A[i - 1] != (tmp + res[i - 1]) % 2:
        res[i - 1] ^= 1
print(sum(res))
ans = [i + 1 for i, v in enumerate(res) if v == 1]
if ans:
    print(*ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
l=[0]*n
for i in reversed(range(1,n+1)):
    x=0
    if n//i>1:
        for j in range(1,n//i):
            x+=l[(j+1)*i-1]
        if (x%2)==a[i-1]:
            l[i-1]=0
        else:
            l[i-1]=1
    else:
        l[i-1]=a[i-1]
m=l.count(1)
print(m)
for i in range(n):
    if l[i]==1:
        print(i+1)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int,input().split()))
k = [0 for i in range(n)]
t = []
for i in range(n-1,-1,-1):
  a = l[i]
  s = 0
  for j in range(i,n,i+1):
    if j ==i:
      continue
    if k[j]==1:
      s += 1
      s %= 2
  if a!=(k[i]+s)%2:
    t.append(i+1)
    k[i] += 1
    k[i] %= 2
    
if len(t)==0:
  print(0)
else:
  print(len(t))
  print(*t)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    A=[int(_) for _ in input().split()]
    B=[0]*n
    for i in range(n-1,-1,-1):
        x=2*(i+1)
        other=0
        while x<=n:
            other+=B[x-1]
            x+=i+1
        if other%2==A[i]:
            B[i]=0
        else:
            B[i]=1
    print(sum(B))
    print(*[int(i+1) for i,x in enumerate(B) if x==1])

if __name__=='__main__':
    main()

Submission status: Accepted

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

c = [ 0 ] * N
for i in range( N , 0, -1 ):
  s = 0
  for j in range( 2, N // i + 1 ):
    s += c[ i * j - 1 ]
  if s % 2 != a[ i - 1 ]:
    c[ i - 1 ] = 1

m = 0
b = ""
for i in range( N ):
  if c[i] > 0:
    m += 1
    b += str( i + 1 ) + " "
print( m )
print( b[:-1] )

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def main():
    N = int(readline())
    A = [0] + [int(i) for i in readline().split()]
    table = [0 for _ in range(N+1)]
    for i in range(N, 0, -1):
        table[i] = (sum(table[::i])%2)^A[i]

    print(sum(table))
    for i in range(N):
        if table[i+1]:
            print(i+1, end=' ')
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def main():
    N = int(readline())
    A = [0] + [int(i) for i in readline().split()]
    table = [0 for _ in range(N+1)]
    for i in range(N, 0, -1):
        table[i] = (sum(table[::i])+A[i])%2

    print(sum(table))
    for i in range(N):
        if table[i+1]:
            print(i+1, end=' ')
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def main():
    N = int(readline())
    A = [0] + [int(i) for i in readline().split()]
    table = [0 for _ in range(N+1)] 
    for i in [int(i) for i in range(1, N+1)][::-1]:
        table[i] = (sum(table[::i])+A[i])%2
    print(sum(table))
    for i in range(N):
        if table[i+1]:
            print(i+1, end=' ')
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def main():
    N = int(readline())
    a = [0]+[int(i) for i in readline().split()]
    table = [0 for _ in range(N+1)]     
    def S(a, i):
        res = 0
        j = i
        while i <= N:
            res += a[i]
            i += j
        return res%2

    for i in reversed(range(1, N+1)):
        x = S(table, i)
        table[i] = (S(table, i)+a[i])%2

    m = sum(table)
    print(m)
    for i in range(1, N+1):
        if table[i]:
            print(i, end=' ')
if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    N = int(input())
    A = list(map(int,input().split()))

    dp = [0] * (N+1)
    box = []
    for i in reversed(range(1,N+1)):
        las = N//i
        dp[i] = A[i-1]
        if las >= 2:
            sum = 0
            for j in range(2,las+1):
                sum += dp[i*j] % 2

            dp[i] -= sum
            dp[i] %= 2

        if dp[i] == 1:
            box.append(i)

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


if __name__ == "__main__":
  main()

Submission status: Accepted

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