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:
# https://note.mu/tanon_cp/n/nf77205916310

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

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

flag=[-1]*N #0～n-1番目の箱にボールを入れたかどうかの情報を入れる
ans=[]
for i in range(N-1,-1,-1):
    cnt=0
    for j in range(i,N,i+1): #i番目以降のiの倍数の箱にボールが何個入っているかを数える
        if j==i:
            continue
        else:
            if flag[j]==1:
                cnt+=1
    if (A[i]+cnt)%2==0: #箱にボールを入れるかの判定
        flag[i]=0
    else:
        flag[i]=1
        ans.append(i+1) #ボールを入れた箱のインデックスを答えに追加
num=len(ans)
if num==0: #ボールを入れた箱がなければ答えは0
    print(0)
else: #ボールを入れた箱があれば入れた箱の数とそのインデックスを出力
    print(num)
    print(*ans)

Submission status: Accepted

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

ans=[]
box=[0]*N

for i in reversed(range(1,N+1)):
  asum=sum(box[i-1::i])
  if asum%2+A[i-1]==1:
    box[i-1]=1
    ans.append(i)

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

Submission status: Accepted

Solution code:
# 2019/10/04

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

for i in range(n):
    idx=n-i
    j=2
    cnt=0
    while idx*j<=n:
        cnt+=b[idx*j]
        j+=1
    cnt%=2
    if cnt==a[idx]:continue
    b[idx]=1
    
smb=sum(b)
print(smb)
for i in range(1,n+1):
    if b[i]:print(i,end=' ')
if smb:print()

Submission status: Accepted

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

for i in range(N//2+1,N+1):
    B[i] = A[i]

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

B.pop(0)

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

print(*ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
num = [i for i in range(n)]
B = [0]*(n)
C = []
ans = 0
for i in range(n-1, -1, -1):
  ms = sum(B[i::i+1])
  if ms % 2 != A[i]:
    ans += 1
    C.append(i+1)
    B[i] = 1
print(ans)
print(*C)

Submission status: Accepted

Solution code:
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)
    return divisors[:1]+divisors[2:]

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

for i in range(N)[::-1]:
  a = A[i]
  if a % 2:
    ans.append(i+1)
  D = md(i+1)
  
  for d in D:
    A[d-1] += a
    
print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
N = int(input())

divisors = [[] for _ in range(N + 1)]

for i in range(1, N + 1):
    num = 2 * i
    while num <= N:
        divisors[num].append(i)
        num += i
ans = []
balls = [0] * (N + 1)
A = [int(x) for x in input().split()]
for i in reversed(range(1, N+1)):
    if balls[i] != A[i-1]:
        ans.append(i)
        balls[i] ^= 1
        for d in divisors[i]:
            balls[d] ^= 1

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

Submission status: Accepted

Solution code:
n = input()
a = [0] + map(int, raw_input().split())
b = [0 for _ in range(n + 1)]
used = []

for i in xrange(n, 0, -1):
  sum = 0
  for j in xrange(2 * i, n + 1, i):
    sum += b[j]
  if sum % 2 != a[i]:
    used.append(i)
    b[i] = 1
print len(used)
for x in used: print x,
print

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(N,0,-1):
  tmp=0
  for j in range(2,N//i+1):
    if B[i*j]: tmp+=1
  B[i]=(A[i]+tmp)%2
  
#print(B)
C=[]
for i in range(1,N+1):
  if B[i]: C.append(i)
#print(C)

print(len(C))
if len(C): print(*C)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def divisors(m: int):
    i = 1
    div = []
    while i * i <= m:
        if m % i == 0:
            div.append(i)
            div.append(m // i)
        i += 1

    return list(set(div))

n = ni()
a = list(li())
b = [0]*n
ans = []
for i in range(n-1, -1, -1):
    if a[i] != b[i]:
        divs = divisors(i+1)
        ans.append(i+1)
        for j in divs:
            b[j-1] += 1
            b[j-1] %= 2

print(len(ans))

if ans:
    print(*ans[::-1])

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
counts = [0] * (N + 1)
ball_counts = 0
balls = []
for i in range(N-1, -1, -1):
    if sum(counts[::i+1][1:]) % 2 != A[i]:
        ball_counts += 1
        balls.append(i+1)
        counts[i+1] = 1
print(ball_counts)
if ball_counts > 0:
    print(*balls)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
L = LI()
A = [0] * n
total = 0
for i in range(n - 1, -1, -1):
    ret = 0
    for j in range((i + 1) * 2 - 1, n, i + 1):
        ret += A[j]
    if L[i] != ret % 2:
        A[i] = 1
        total += 1



print(total)
for k in range(n):
    if A[k]:
        print(k + 1)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))

    filled = [0]*(n+1)
    ans = []
    for i in range(n-1, -1, -1):
        if sum(filled[::i+1][1:]) % 2 != A[i]:
            filled[i+1] = 1
            ans.append(i+1)
    print(len(ans))
    print(' '.join(map(str, ans)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, *a = map(int, open(0).read().split())

    a = [0] + a
    b = [0] * (n + 1)
    for i in range(1, n+1)[::-1]:
        if i * 2 > n:
            b[i] = a[i]
        else:
            rem = 0
            for j in range(i * 2 , n + 1, i):
                rem = rem ^ b[j]
            b[i] = rem ^ a[i]

    b = b[1:]
    m = sum(b)
    print(m)
    for i, cur_b in enumerate(b, start=1):
        if cur_b == 1:
            print(i, end=' ')
    return()

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
a = [int(i) for i in input().split()]
zeros = [0] * N
length = len(a)

for i, ai in zip(a[::-1], range(length, -1, -1)):
    s = 0
    for j in range(ai, length+1, ai):
        s += zeros[j-1]
    if s % 2 == i:
        pass
    else:
        zeros[ai-1] = 1

print(sum(zeros))
for i, v in enumerate(zeros, 1):
    if v:
        print(i, end=" ")

Submission status: Accepted

Solution code:
n=int(input())
a= list(map(int, input().split()))
li=[0 for _ in range(n)]
for i in range(n-1,-1,-1):
    check=0
    for j in range(n//(i+1)):
        check^=li[(i+1)*(j+1)-1]
    if check!=a[i]:
        li[i]+=1
ans=[i+1 for i, x in enumerate(li) if x == 1]
print(len(ans))
print(" ".join(map(str,ans)))

Submission status: Accepted

Solution code:
N = int(input())
a = [int(i) for i in input().split()]
zeros = [0] * N
ai = length = len(a)

for i in a[::-1]:
    s = 0
    for j in range(ai, length+1, ai):
        s += zeros[j-1]
    if s % 2 == i:
        pass
    else:
        zeros[ai-1] = 1
    ai -= 1

print(sum(zeros))
for i, v in enumerate(zeros, 1):
    if v:
        print(i)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0 for i in range(N)]

out = []
for i in range(N, 0, -1):
    a = A[i - 1]
    q = N // i
    count = 0
    
    for j in range(2, q+1):
        if B[i * j - 1] == 1:
            count += 1
    
    r = count % 2
    
    if a == 0:
        if r == 1:
            B[i - 1] = 1
            out.append(i)
        else:
            B[i - 1] = 0
    else:
        if r == 1:
            B[i - 1] = 0
        else:
            B[i - 1] = 1
            out.append(i)
g = sum(B)
print(g)
    
if g != 0:
    print(*out)

Submission status: Accepted

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

b = [0]*N

for i in range(N):
    j = N-i
    k = 2*j
    context = 0
    while k<=N:
        context+=b[k-1]
        k+=j
    if context%2==a[j-1]:
        b[j-1]=0
    else:
        b[j-1]=1

M=sum(b)

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

print(M)
print(*ans)

Submission status: Accepted

Solution code:
n=int(input())
lists=list(map(int,input().split()))
lists.insert(0,0)
anslists=[0]*(n+1)
for j in range(n,0,-1):
# j=n,n-1,.......,2,1という感じ
    numbers=n//j
    if numbers==1:
        anslists[j]=lists[j]
    else:
        check=0
        for i in range(2,numbers+1):
            check+=anslists[i*j]
            
        if check%2==0:
            anslists[j]=lists[j]
            
        else:
            
            if lists[j]==1:
                anslists[j]=0
                
            if lists[j]==0:
                anslists[j]=1
                

printA=0

del anslists[0]


Anslist=[]
for k in range(n):
    if anslists[k]==1:
        printA+=1
        Anslist.append(k+1)
print(printA)
print(*Anslist)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
B = [0]*n
ans = []
cur = 0
for i in range(n,0,-1):
	# print("i",i)
	j = i
	cur = 0
	k = 1
	while j*k <= n:
		# print("j*k",j,k,cur)
		cur += B[j*k-1]
		k += 1
	if cur % 2 != A[i-1]:
		ans.append(i)
		B[i-1] = 1
	# print(B,ans)
print(len(ans))
if ans:
	print(*ans[::-1])

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
ans= []
B = [0]*n
for i in reversed(range(n)):
  if sum(B[i::i+1])%2!=A[i]:
    ans.append(i+1)
    B[i]+= 1
print(len(ans))   
print(*ans)

Submission status: Accepted

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

a.insert(0,0)

ans = [0]*(n+1)

for i in range(n,0,-1):
    value = 0
    for j in range(2*i,n+1,i):
        value = value ^ ans[j]
    ans[i] = value ^ a[i]
print(sum(ans))
for i in range(1,n+1):
    if ans[i] == 1:
        print(i,end = " ")

Submission status: Accepted

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

B = [0] * N
n = [i+1 for i in range(N)]
for i in range(N)[::-1]:
  if sum(B[i::i+1]) % 2 != A[i]:
    B[i] = 1

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

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):
    cnt = 0
    for j in range(i, N, i+1):
        cnt += b[j]
    b[i] = (cnt + a[i]) % 2
    
print(sum(b))
print(*[i+1 for i in range(N) if b[i]==1])

Submission status: Accepted

Solution code:
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import sys
import logging
import heapq
logging.basicConfig(level=logging.DEBUG)

input = sys.stdin.readline

setrecursionlimit(1000000)

MOD = 10**9+7

def main():
    N=int(input())
    A=[None]+[int(x) for x in input().split()]

    ans=[]
    check=[None]+[0]*N

    for i in reversed(range(1,N+1)):
        # print(i)
        # print(check[i::i])
        if not sum(check[i::i])%2 == A[i]:
            check[i]=1
            ans.append(i)

    # print(A)
    # print(check)
    print(len(ans))
    print(*ans)

main()

Submission status: Accepted

Solution code:
N =int(input())
a_list = list(map(int, ("0 " + input()).split()))
put_list = [0] * (N+1)
count = 0
in_list = []
for index in reversed(range(len(a_list))):
    if index == 0:
        break
    upper_index_keisuu = 2
    upper_sum = 0
    while True:
        if index * upper_index_keisuu > (len(a_list)-1):
            break
        upper_sum += put_list[index * upper_index_keisuu]
        upper_sum %= 2
        upper_index_keisuu += 1

    if upper_sum != a_list[index]:
        count += 1
        put_list[index] = 1
        in_list.append(index)


print(count)

if count > 0:
    ret_str = ""
    for add in in_list:
        ret_str += str(add) + " "
    print(ret_str)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = []
C = [0] * n
for i in reversed(range(n)):
    if sum(C[i::i+1]) % 2 != A[i]:
        B.append(i+1)
        C[i] += 1
print(len(B))
print(' '.join(map(str, B)))

Submission status: Accepted

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    ls = [0] * n
    cnt = 0
    ans = []
    for i in range(n-1, -1, -1):
        t = 0
        for j in range(i, n, (i + 1)):
            t += ls[j]
        if t % 2 != a[i]:
            ls[i] += 1
            cnt += 1
            ans.append(i + 1)
    print(cnt)
    if cnt != 0:
        print(*ans)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
n=int(input())
a=[None]+[int(i) for i in input().split()]

check=[0]*(n+1)
ans=[]

for i in range(n,0,-1):
    if sum(check[2*i::i])%2==a[i]:
        continue
    else:
        check[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 for i in range(n)]
for i in range(1,n + 1)[::-1]:
    count = 0
    mul = 1
    k = i
    while k * mul <= n:
        count += Ans[k * mul - 1]
        mul += 1
    if count % 2 != a[i - 1]:
        Ans[i - 1] = 1
print(sum(Ans))
for i in range(1, n + 1):
    if Ans[i - 1] == 1:
        print("{} ".format(i), end = " ")

Submission status: Accepted

Solution code:
n=int(input())
a = [int(i) for i in input().split()]
b = [0] * n


for i in range(n, 0, - 1):
    k=0
    for j in range(2*i-1, n, i):
        k ^= b[j] & 1
    b[i - 1] = k ^ a[i - 1]
print(sum(b))
for i, j in enumerate(b):
    if j == 1:
        print(i+1)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)
B = [0] * (N + 1)
for i in reversed(range(1, N + 1)):
    sum_val = 0
    for j in range(i*2, N + 1, i):
        sum_val ^= B[j]
    B[i] = sum_val ^ A[i]

ans = [str(idx) for idx, val in enumerate(B) if val == 1]
print(len(ans))
print(" ".join(ans))

Submission status: Accepted

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

a.insert(0, 0) # 0番目に0をinsertして0indexed
ans = [0 for _ in range(N+1)]

for i in range(N, 0, -1): # iはNから1
    tmp = 0
    for j in range(2*i, N+1, i): # jは2i, 3i, 4i, ...(最大はN)
        tmp ^= ans[j] # 1, 0, 1, 0...を繰り返す(偶数個入ってたら0, 奇数個入ってたら1)
    ans[i] = tmp ^ a[i] # aに合わせてansに入れる

print(sum(ans)) # 入っているボールの個数
for i in range(1, N+1):
    if ans[i] == 1:
        print(i, end=' ')
else:
    print()

Submission status: Accepted

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

for i in range(n, 0, -1):
    if i > n//2:
        if a[i-1] == 1:
            box[i-1] += 1
    elif i == 1:
        if a[0] != (sum(box) % 2):
            box[0] += 1
    elif a[i-1] != (sum(box[i-1:: i]) % 2):
        box[i-1] += 1

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

print(m)
for x in b:
    print(x, end=' ')

Submission status: Accepted

Solution code:
#D
from collections import deque
n=int(input())
a=deque(list(map(int,input().split())))
a.appendleft(0)
b=[0 for i in range(n+1)]
c=[]
m=0
for i in range(n):
    k=2
    sum=0
    while (n-i)*k<=n:
        sum+=b[(n-i)*k]
        k+=1
    if sum%2!=a[n-i]:
        b[n-i]=1
        c.append(n-i)
        m+=1
print(m)
c.sort()
c=list(map(str,c))
print(" ".join(c))

Submission status: Accepted

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

memo = [0] * N
for i in range(1, N+1)[::-1]:
    sm = sum([memo[j-1] for j in range(i, N+1, i)])
    memo[i-1] = (sm + a[i-1]) % 2

M = sum(memo)
print(M)

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

Submission status: Accepted

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

res = [0] * (n + 1)

for i in range(1, n + 1)[::-1]:
    sum_res = sum(res[x] for x in range(i, n + 1, i))
    if sum_res % 2 != arr[i - 1]:
        res[i] = 1

print(sum(res))

if sum(res):
    ans = []
    for i, elm in enumerate(res):
        if elm:
            ans.append(i)
    print(*ans)

Submission status: Accepted

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

MOD = 2  # type: int


def solve(N: int, a: "List[int]"):
    # ボールの数をカウント
    tf = [0] * N
    # ボールの数をカウント
    m = 0
    x = []
    for i in range(N-1, -1, -1):
        # iの倍数の箱に入ったボールを求める
        b = sum([tf[j] for j in range(i+(i+1), N, i+1)])
        if(b%2 != a[i]):
            m += 1
            x.append(i+1)
            tf[i] = (tf[i]+1)%2
        
    print(m)
    if(x):
        print(' '.join(map(str, x)))

    return


# Generated by 1.1.5 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

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))

    ans = [False for i in range(n)]

    for i in range(n-1, -1, -1):
        num = i + 1
        j = 2
        accum = 0
        while num * j <= n:
            accum = (accum + ans[num * j - 1]) % 2
            j += 1
        ans[i] = (not accum == a[i])

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans_list = [0 for _ in range(n)]

for i in range(n-1, -1, -1):
    prev = 0
    index = i+1
    for j in range(2, n+1):
        if (index * j)-1 >= n: break
        prev += ans_list[(index * j)-1]
    if prev % 2 != a[i]:
        ans_list[i] = 1

print(sum(ans_list))
if sum(ans_list) != 0:
    print(' '.join([str(i+1) for i, x in enumerate(ans_list) if x == 1]))

Submission status: Accepted

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
A = LIST()
ans = [0]*n
for i in range(n-1,-1,-1):
    res = 0
    j = 0
    while (j+1) *(i+1) <= n:
        res += ans[(j+1)*(i+1)-1]
        j += 1
    if res%2 != A[i]:
        ans[i] = 1
print(ans.count(1))
for i in range(n):
    if ans[i] == 1:
        print(str(i+1)+' ', end = '')

Submission status: Accepted

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

for _i in range(N):
    i = N-_i
    cur = i * 2
    sum_b = 0
    # print('i', i)

    if i == 0:
        break

    while cur <= N:
        # print(i-1, cur)
        sum_b += B[cur-1]
        cur += i

    b = (sum_b + A[i-1]) % 2

    # print(i, b)
    if b == 1:
        B[i-1] = b
        bc += 1

# print(B)
print(bc)
if bc > 0:
    print(' '.join([str(i+1) for i in range(N) if B[i] > 0]))

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int,input().split()))
pattern = [0 for _ in range(N)]


for i in range(1,N+1)[::-1]:
    count = 0
    if i > N//2:
        pattern[i-1] = As[i-1]

    else:
        for j in range(2,N//i+1):
            count += pattern[i*j-1]
        if count % 2 == As[i-1]:
            pattern[i-1] = 0
        else:
            pattern[i-1] = 1
s = sum(pattern)
print(s)
if s:
    s = ""
    for i,e in enumerate(pattern):
        if e == 1:
            s += str(i+1)
            s += ' '

    print(s[:-1])

Submission status: Accepted

Solution code:
import sys

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

for i in reversed(range(n)):
	sum_a = 0
	for j in range(i,n,i+1):
		sum_a += b[j]
	if sum_a % 2 == a[i]:
		b[i] = 0
	else:
		b[i] = 1

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

if not ans:
	print("0")
else:
	print(m)
	for i,x in enumerate(ans):
		if i == 0:
			sys.stdout.write(str(x))
		else:
			sys.stdout.write(" ")
			sys.stdout.write(str(x))

Submission status: Accepted

Solution code:
import sys
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]
ball_ls = [0 for i in range(n)]
for i in range(n-1,-1,-1):
    if i > n / 2 - 1:
        ball_ls[i] = a_ls[i]
    else:
        ball_ls[i] = (sum(ball_ls[i::(i + 1)]) + a_ls[i]) % 2
cnt = sum(ball_ls)
ball_ls = [str(i+1) for i, ball in enumerate(ball_ls) if ball > 0]
print(cnt)
if cnt > 0:
    print(" ".join(ball_ls))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]

cs = [0] * N

for i in range(N):
    j = N - i
    cs[j - 1] = (A[j-1] + sum(cs[j - 1::j])) % 2

rs = []
for i, v in enumerate(cs):
    if v:
        rs.append(i + 1)

print(len(rs))
print(*rs)

Submission status: Accepted

Solution code:
#134ABCD - Preparing Boxes
#部分的WA
import math
N = int(input())
a = list(map(int,input().split()))
ball = [0]*N
for i in range(N,0,-1):
    #print(ball)
    stock = 0
    for j in range(i,N+1,i):
        stock += ball[j-1]
        #print(stock)
    if stock %2 == 1:
        if a[i-1] ==1:
            ball[i-1] += 0
        elif a[i-1] == 0:
            ball[i-1] += 1
    elif stock %2 == 0:
        if a[i-1] ==1:
            ball[i-1] += 1
        elif a[i-1] == 0:
            ball[i-1] += 0
#print(ball)
#ans = [str(k) for k in ball]
#print(' '.join(ans))#int型ではjoinは使えない
ans1 = []
count = 0
for k in range(N):
    if ball[k] == 1:
        ans1.append(k+1)
        count += 1
ans2 = [str(l) for l in ans1]
print(count)
print(' '.join(ans2))

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
M = [0 for i in range(n)]
for i in reversed(range(1,n+1)):
    k = 0
    j = 2*i
    while j<=n:
        if M[j-1] == 1:
            k += 1
        j += i
    if (k+1)%2 == A[i-1]:
        M[i-1] = 1
B = []
for i in range(n):
    if M[i] == 1:
        B += [i+1]
print(len(B))
if len(B) > 0:
    print(*B)

Submission status: Accepted

Solution code:
def solve(n, a):
    b = [-1] * n
    for i in range(n, 0, -1):
        cnt = 0
        for j in range(2*i, n+1, i):
            cnt += b[j-1]
        p = cnt % 2
        b[i-1] = p ^ a[i-1]
    res = []
    for i, v in enumerate(b):
        if v > 0:
            res.append(i+1)
    m = len(res)
    print(m)
    if m > 0:
        print(" ".join(map(str, res)))

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

Submission status: Accepted

Solution code:
def solve(string):
    n, *a = map(int, string.split())
    for i in range(n // 2, 0, -1):
        a[i - 1] = sum(a[i - 1::i]) % 2
    ans = [str(i + 1) for i, _a in enumerate(a) if _a == 1]
    return "0" if len(ans) == 0 else "{}\n{}".format(len(ans), " ".join(ans))


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
import numpy as np


def solve(string):
    n, *a = map(int, string.split())
    a = np.asarray([0] + a)
    for i in range(n // 2, 0, -1):
        a[i] = a[i::i].sum() % 2
    ans = np.where(a == 1)[0]
    return "0" if len(ans) == 0 else "{}\n{}".format(len(ans), " ".join(map(str, ans)))


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
from math import ceil


def solve(string):
    n, *a = map(int, string.split())
    t = [0] * n
    ans = []
    for i, _a in zip(range(n, 0, -1), a[::-1]):
        if t[i - 1] % 2 == _a:
            continue
        ans.append(str(i))
        for j in range(1, ceil((i + 1)**0.5)):
            if i % j == 0:
                t[j - 1] += 1
                if j != i // j:
                    t[i // j - 1] += 1
    return "0" if len(ans) == 0 else "{}\n{}".format(len(ans), " ".join(ans[::-1]))

  
if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
B = [0] * N
ans = []
for i in range(N, 0, -1):
    y = 1
    x = i * y
    s = 0
    while x <= N:
        s += B[x-1]
        y += 1
        x = i * y
    if s % 2 != A[i-1]:
        B[i-1] = 1
        ans.append(i)

M = sum(B)
ans = map(str, ans)
ans = " ".join(ans)

print(M)
print(ans)

Submission status: Accepted

Solution code:
# ABC134D - Preparing Boxes
def main():
    N, *A = map(int, open(0).read().split())
    A = [0] + A
    for i in range(N // 2, 0, -1):  # second half: no multiples
        A[i] = sum(A[i::i]) % 2
    ans = [i for i, j in enumerate(A) if j]
    print(len(ans))
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
a_list = list(map(int, input().split()))
b_list = [0 for _ in range(N)]
ans_list = []
ballN = 0
for i in range(N, 0, -1):
    y = 2
    x = i * y
    while x <= N:
        ballN += b_list[x-1]
        y += 1
        x = i * y
    if ballN % 2 == a_list[i - 1]:
        ballN = 0
        continue
    else:
        b_list[i-1] = 1
        ans_list.append(i)
        ballN = 0



ans = map(str, ans_list)
ans = " ".join(ans)

M = sum(b_list)
print(M)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10 ** 7)

MOD = 2  # type: int


def solve(N: int, a: "List[int]"):
    ans = [0 for x in range(N)]
    for i in range(N - 1, -1, -1):
        s = 0
        for j in range(i, N, i + 1):
            s += ans[j]
        # print(s, a[i], s ^ a[i])
        if (s + a[i]) & 1:
            ans[i] = 1
    # print(ans)
    b = int(sum(ans))
    print(b)
    l = []
    if b:
        for i, x in enumerate(ans):
            if x == 1:
                l.append(i + 1)
        print(*l)
    return


# Generated by 1.1.5 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
input = sys.stdin.readline

n = int(input())
a_list = [-1]
a_tmp = list(map(int, input().split()))
a_list.extend(a_tmp)

ball_list = [0]*(n+1)


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

    sum_ball = 0
    for j in range(2, div+1):
        sum_ball += ball_list[i*j]

    if a_list[i] == 1:
        if sum_ball % 2 == 0:
            ball_list[i] = 1
    else:
        if sum_ball % 2 == 1:
            ball_list[i] = 1

sb = sum(ball_list)
print(sb)
if sb != 0:
    p_a = [str(i) for i in range(1, n+1) if ball_list[i] == 1]
    print(' '.join(p_a))

Submission status: Accepted

Solution code:
N = int(input())

A = [0] + [int(_) for _ in input().split()]
ans = [0] * (N + 1)

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

# print(ans)
spam = [i for i in range(1, N + 1) if ans[i]]
print(len(spam))
if spam:
    print(*spam)