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())
A = [0]
A.extend(list(map(int, input().split())))
boxes = [0] * (N+1)

for i in range(N, 0, -1):
    # print(i)
    wa = 0
    for j in range(i, N+1, i):
        # print(j)
        wa += boxes[j]
    if wa % 2 != A[i]:
        boxes[i] = 1
    # print("hogeeeeeeeeee")
ans = []
for i in range(len(boxes)):
    if boxes[i] == 1:
        ans.append(i)

print(len(ans))
if len(ans) != 0:
    print(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [1]*N
# 参照する数の少ない後ろからチェックしていく
for i, ai in enumerate(reversed(A)):
  count = 0
# N-iの倍数番号の和をカウントし2で割った余りがaiと一致しなければBのN-i番目を0に変更
  for j in range(N-i, N+1, N-i):
    count += B[j-1]
  if ai != count%2:
    B[N-1-i] = 0
# MはBの1の数、Bの要素が1のインデックスを取得してリスト化、展開
M = sum(B)
l = [i+1 for i, bi in enumerate(B) if bi == 1]
print(M)
print(*l)

Submission status: Accepted

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


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

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-1,-1,-1):
  isum = 0
  itr = 2
  while (i+1)*itr -1 < N:
    isum += B[(i+1)*itr - 1]
    itr += 1
  isum %= 2
  if isum != A[i]:
    B[i] = 1

if sum(B) == 0:
  print(0)
else:
  print(sum(B))
  for i in range(N):
    if B[i] != 0:
      print(i+1)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [0]*n
tmp=[]
ans=""
for i in range(n-1,-1,-1):
  num = i+1
  total=0
  j=1
  while (i+1)*j <= n:
    total+=b[((i+1)*j)-1]
    j+=1  
  if total%2==a[i]:
    b[i]=0
  else:
    b[i]=1
    tmp.append(i+1)

print(sum(b))
print(str(sorted(tmp)).replace(',','').replace('[','').replace(']',''))

Submission status: Accepted

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

boxes = [0 for i in range(N+1)]  # 後に最初の要素を取り除く

for i in range(N, 0, -1):
    # print("iiii = ", i)
    wa = 0
    for j in range(i, N+1, i):
        # print("j = ", j)
        wa += boxes[j]
    if wa % 2 != A[i]:
        boxes[i] = 1

ans_n = sum(boxes)
ans_list = []

for i in range(len(A)):
    if boxes[i] == 1:
        ans_list.append(i)
print(ans_n)
if ans_n != 0:
    print(" ".join(map(str, ans_list)))

Submission status: Accepted

Solution code:
n = int(input())
a = [0] + list(map(int, input().split()))
ans = set()
b = [0] * (n + 1)
for i in range(n, 0, - 1):
    cnt = 0
    for j in range(i, n + 1, i):
        cnt += b[j]
    cnt %= 2
    b[i] = (a[i] % 2) - cnt
    if b[i] :
        ans.add(i)
print(len(ans))
print(*ans)

Submission status: Accepted

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

ans = a[:]

for i in range(n//2, 0, -1):
    cnt = 0
    for times in range(i, n+1, i):
        cnt += ans[times-1]
    if cnt%2 != a[i-1]:
        ans[i-1] = (ans[i-1]+1)%2

print(sum(ans))
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]*n
ans=[]
anscnt=0
for i in range(n-1,-1,-1):
    ai=a[i]
    j=2*(i+1)-1
    while n>j:
        ai^=b[j]
        j+=i+1
    if ai==1:
        b[i]=1
        ans.append(i+1)
        anscnt+=1
print(anscnt)
if anscnt>0:
    ans.reverse()
    print(*ans)

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))

N = int(input())
A = [0] + inpl()
D = [0]*(N+1)

for i in range(N, 0, -1):
    D[i] = (sum(D[2*i::i])%2)^A[i]
print(sum(D))
print(*[i for i in range(N+1) if D[i]])

Submission status: Accepted

Solution code:
n = int(input())
data = [int(_) for _ in input().split(" ")]

for i in range(len(data),0,-1):
    count = n//i
    total = 0
    for k in range(count,1,-1):
        total += data[i*k-1]
    if data[i-1]%2 == 0 and total%2 == 0:
        data[i-1] = 0
    elif data[i-1]%2 == 1 and total%2 == 1:
        data[i-1] = 0
    else:
        data[i-1] = 1

m = 0
for ele in data:
    if ele != 0:
        m += 1

print(m)
if m != 0:
    ans = []
    for i in range(len(data)):
        if data[i] != 0:
            ans.append(i+1)
    print(" ".join(map(str,ans)))

Submission status: Accepted

Solution code:
import sys

#+++++


def oaa(a_ll, val, oe):
	#print(ll,val,oe)
	if val == 1:
		s=sum(a_ll)
	else:
		c=1
		s=0
		lll=len(a_ll)
		s=sum(a_ll[val-1::val])
		#print(a_ll, val, a_ll[val-1::val], s)
		#while c * val <= lll:
		#	s+=ll[(c*val)-1]
		#	c+=1
	return 1 if oe != s%2 else 0
		
def main():
	n = int(input())
	ll= list(map(int, input().split()))
	
	ret = [0 for _ in range(n)]
	for i in range(n):
		val=n-i
		rr=oaa(ret, val, ll[-i-1])
		ret[-i-1]=rr
	
	#print(ret)
	print(sum(ret))
	print(' '.join([str(i+1) for i,v in  enumerate(ret) if v == 1]))
		
		
	
#+++++

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
	else:
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
n = int(input())
A = [0] + [int(a) for a in input().split()]
B = [0]*(n+1)
B[-1] = A[-1]
for i in range(n-1,0,-1):
    a = A[i]
    for j in range(i,n+1,i):
        a += B[j]
    B[i] = a%2
s = sum(B)
print(s)
if s != 0:
    print(*[idx for idx,b in enumerate(B) if b==1])

Submission status: Accepted

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

for i in range(n-1, -1, -1):
    j = i + 1
    ball = B[i::j]
    if sum(ball) % 2 != A[i]:
        B[i] = 1

print(sum(B))

B_ball = [str(i+1) for i in range(n) if B[i] == 1]
print(" ".join(B_ball))

Submission status: Accepted

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


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

b = b[1:]
b_index = []
for i, n in enumerate(b):
    if n == 1:
        b_index.append(str(i+1))

print(len([n for n in b if n == 1]))
if len(b_index) > 0:
    print(' '.join(b_index))

Submission status: Accepted

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

b = [0] * n
for i in range(n)[::-1]:
    multiple = b[i::i + 1]
    if sum(multiple) % 2 != a[i]:  # 偶奇が一致していない場合
        b[i] = 1  # ボールを入れる
    
print(sum(b))
true_b = []  # ボールが入っている箱の番号 true_b
for i in range(n):
    if b[i] == 0: continue
    true_b.append(str(i + 1))

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

Submission status: Accepted

Solution code:
N = int(input())
a = []
a = list(map(int,input().split()))
 
b = [0]*N
for i in reversed(range(N)):
    j = i + 1
    buf = b[i::j]
    if (sum(buf) % 2) != a[i]:
        b[i] = 1
print(sum(b))
bb = [i+1 for i in range(N) if b[i] == 1]
if sum(b) != 0:
    print(' '.join(map(str, bb)))

Submission status: Accepted

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

b = [0]*N
for i in reversed(range(N)):
    j = i + 1
    buf = b[i::j]
    if (sum(buf) % 2) != a[i]:
        b[i] = 1
print(sum(b))
bb = [i+1 for i in range(N) if b[i] == 1]
if sum(b) != 0:
    print(' '.join(map(str, bb)))

Submission status: Accepted

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

for i in range(n,0,-1):
    s=0
    c=n//i
    if c == 1:
        b[i-1]=a[i-1]
    else:
        for j in range(1,c+1):
            s += b[i*j-1]
        if (s+a[i-1]) % 2 == 1:
            b[i-1]=1
for k in range(0,n):
    if b[k]==1:
        l.append(k+1)

print(len(l))
for m in l:
    print(m)

Submission status: Accepted

Solution code:
def get_divisor(i, n):
    out = [0] * (n // i)
    for j in range(len(out)):
        out[j] = i * (j+1)
    return out

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

B = [False] * n

for i in range(n, 0, -1):
    divisors = get_divisor(i, n)
    B[i-1] = bool(A[i-1]) ^ bool(sum(B[divisor-1] for divisor in divisors) % 2)

out = [str(i+1) for i in range(n) if B[i]]

print(sum(B))
print(" ".join(out))

Submission status: Accepted

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

Submission status: Accepted

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

b = [0] * (N + 1)
half = N // 2
b[half + 1:] = A[half:]
for i in range(half, 1, -1):
    s = sum([b[j] for j in range(i * 2, N + 1, i)]) % 2
    if s != A[i - 1]:
        b[i] = 1
s = sum(b)
if s % 2 != A[0]:
    b[1] = 1
    s += 1
print(s)
print(*[i for i in range(1, N + 1) if b[i] == 1])

Submission status: Accepted

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

b = [0] * (N + 1)
half = N // 2
b[half + 1:] = A[half:]
for i in range(half, 1, -1):
    s = sum([b[j] for j in range(i * 2, N + 1, i)]) % 2
    if s != A[i - 1]:
        b[i] = 1
s = sum(b)
if s % 2 != A[0]:
    b[1] = 1
    s += 1
print(s)
for i, b_ in enumerate(b[:]):
    if b_ == 1:
        print(i, end=" ")

Submission status: Accepted

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

box = [0] * N
v = N // 2  # 後半部の最初のindex

for i in range(v, N):
    if ai[i] == 0:
        box[i] = 0
    else:
        box[i] = 1

for i in range(v - 1, -1, -1):
    value = i + 1
    sum = 0
    for j in range(value * 2 - 1, N, value):
        sum += box[j]
    if sum & 1 == 1:
        box[i] = 0 if ai[i] & 1 == 1 else 1
    else:
        box[i] = 0 if ai[i] & 1 == 0 else 1
print(box.count(1))
for i in range(N):
    if box[i] == 1:
        print(i + 1)

Submission status: Accepted

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

for i in range(N,0,-1):
  kari=a[i]
  for j in range(2,N+1):
    if i*j <= N:
      kari=kari+c[i*j]
    else:
      break
  c[i]=kari%2
M=sum(c)
b = [i for i in range(1,N+1) if c[i] ==1]
b2 = ' '.join(map(str,b))
print(M)
if M>0:
  print(b2)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
x = [0]*n
for i in range(n,0,-1):
    m,c = 2,0
    while i*m<=n:
        c+=x[i*m-1]
        m+=1
    x[i-1] = (a[i-1]+c%2)%2
print(sum(x))
for i in range(n):
    if x[i]: print(i+1)

Submission status: Accepted

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
length = n
ans=0
for i in range(n):
    x = length-i-1
    tmp1 = length-i
    tmp2 = tmp1*2
    while tmp2 <= n:
        if a[tmp2-1]%2==1:
            a[x]+=1
        tmp2 += tmp1
    if a[x]%2==1:
        ans+=1
print(ans)
for i in range(n):
    if a[i]%2 == 1:
        print(i+1,end=" ")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.insert(0,0)
b = [0]*(n+1)
cnt = 0
for i in range(n,0,-1):
    #print(i)
    for j in range(1,n+1):
        #print(j)
        if(i*j>n):
            break
        else:
            cnt += b[i*j]
    if((cnt%2==0 and a[i]==0) or (cnt%2==1 and a[i]==1)):
        b[i] = 0
    elif((cnt%2==0 and a[i]==1) or (cnt%2==1 and a[i]==0)):
        b[i] = 1
    else:
        b[i]=a[i]
    cnt = 0

m = sum(b)
print(m)
for k in range(1,n+1):
    if(b[k]==1):
        print(k,end=' ')
#print('')
# print(a)
#print(b)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import itertools as ite
import math
import random
import sys
import codecs
from collections import defaultdict

INF = 10 ** 18
MOD = 10 ** 9 + 7

sys.setrecursionlimit(1000000)

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

ans = [0] * (N + 1)

for i in range(1, N + 1)[::-1]:
    cnt = 0
    for j in range(i * 2, N + 1, i):
        cnt += ans[j]
    cnt %= 2
    if a[i - 1] != cnt:
        ans[i] = 1
ls = []
for i in range(1, N + 1):
    if ans[i]:
        ls += [i]
print len(ls)
if len(ls) == 0:
    exit()
print " ".join(map(str, ls))

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().rstrip()


def main():
    n = int(input())
    bits = [int(e) for e in input().split()]
    ans = set()
    for i in reversed(range(n)):
        for j in range(i + (i + 1), n, i + 1):
            bits[i] ^= bits[j]
        if bits[i] == 1:
            ans.add(i + 1)
    print(len(ans))
    print(*ans)


main()

Submission status: Accepted

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

ans_lis = [0] * N
to_print_lis = []

for n in range(N - 1, -1, -1):
    sum_lis = sum(A[n: : n + 1])
    tmp_lis = ans_lis[n: : n + 1]
    if sum(tmp_lis) % 2 != A[n]:
        ans_lis[n] = 1
        to_print_lis.append(n + 1)
    #print(ans_lis)
print(len(to_print_lis))
print(*to_print_lis)

Submission status: Accepted

Solution code:
m = int(input())
s = list(map(int, input().split()))
bs = [0] * m

cnt = 0
for i in range(m, 0, -1):
  b = sum(list(map(lambda x: bs[x-1], list(range(i, m+1, i)))))
  if s[i-1] is 0:
    if  b%2 is 0:
      bs[i-1] = 0
    else:
      cnt += 1
      bs[i-1] = 1
  else:
    if  b%2 is 0:
      cnt += 1
      bs[i-1] = 1
    else:
      bs[i-1] = 0

print(cnt)
if cnt > 0:
  print(" ".join([str(i+1) for i, b in enumerate(bs) if b > 0]))

Submission status: Accepted

Solution code:
n = int(input())
an = [int(i) for i in input().split()]
ans = ''

if sum(an)==0:
  print(0)
  exit()

for i in range((n//2)-1,-1,-1):
  an[i] =  sum(an[i*2+1::i+1])%2 ^ an[i]  

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    A = inputList()
    
    ans = [0]*N
    B=[]
    ans_str = ""
    for i in range(N, 0, -1):
        cons = 0
        for j in range(i, N+1, i):
            if ans[j-1] == 1:
                cons += 1
        if A[i-1] == 1 and cons % 2 == 0:
            ans[i-1] = 1
            B.append(i)
            continue
        if A[i-1] == 0 and cons % 2 == 1:
            ans[i-1] = 1
            B.append(i)
            continue
            
    print(len(B))
    print(*B)
            	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    A = inputList()
    
    ans = [0]*N
    B=[]
    ans_str = ""
    for i in range(N, 0, -1):
        cons = 0
        for j in range(i, N+1, i):
            if ans[j-1] == 1:
                cons += 1
        if A[i-1] == 1 and cons % 2 == 0:
            ans[i-1] = 1
            B.append(i)
            #ans_str = ans_str + str(i) + " "
            continue
        if A[i-1] == 0 and cons % 2 == 1:
            ans[i-1] = 1
            B.append(i)
            #ans_str = ans_str + str(i) + " "
            continue
            
    print(len(B))
    print(*B)
            	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    A = inputList()
    
    ans = [0]*N
    B=[]
    for i in range(N, 0, -1):
        cons = 0
        for j in range(i, N+1, i):
            if ans[j-1] == 1:
                cons += 1
        if A[i-1] == 1 and cons % 2 == 0:
            ans[i-1] = 1
            B.append(i)
            continue
        if A[i-1] == 0 and cons % 2 == 1:
            ans[i-1] = 1
            B.append(i)
            continue
            
    print(len(B))
    print(*B)
            	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    A = inputList()
    
    ans = [0]*N
    B=[]
    for i in range(N, 0, -1):
        cons = 0
        for j in range(i, N+1, i):
            cons ^= ans[j-1]
        if A[i-1] != cons:
            ans[i-1] = 1
            B.append(i)
            continue
        if A[i-1] != cons:
            ans[i-1] = 1
            B.append(i)
            continue
            
    print(len(B))
    print(*B)
            	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
 
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7
 
N=INT()
A=LIST()
 
# その位置にボールを入れるかを保持するA2
A2=[0]*N
B=[]
# 後ろから決めていく
for i in range(N-1, -1, -1):
    cur=i+1
    cnt=0
    # curの倍数を全部見に行く
    for j in range(cur*2, N+1, cur):
        cnt^=A2[j-1]
    # ボールを入れるべきかどうか
    if A[i]!=cnt:
        B.append(cur)
        A2[i]=1
 
print(len(B))
print(*B)

Submission status: Accepted

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

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

s = sum(A[0:N])
print(s)

n = 1
for i in range(N):
    if A[i] == 1:
        if n == s:
            print(i+1)
            break
        else:
            print(i+1,end=' ')
            n += 1

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
A=LIST()

# その位置にボールを入れるかを保持するA2
A2=[0]*N
B=[]
# 後ろから決めていく
for i in range(N-1, -1, -1):
    cur=i+1
    cnt=0
    # curの倍数を全部見に行く
    for j in range(cur*2, N+1, cur):
        cnt^=A2[j-1]
    # ボールを入れるべきかどうか
    if A[i]!=cnt:
        B.append(cur)
        A2[i]=1

print(len(B))
print(*B)

Submission status: Accepted

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

for i in range(n, 0, -1):
    s = 0
    c = n // i
    if c == 1:
        b[i-1] = a[i-1]
    else:
        for j in range(1, c+1):
            s += b[i*j-1]
        if (s+a[i-1])%2 == 1:
            b[i-1] = 1
    #print("n:" + str(i) + " c:" + str(c) + " s:" + str(s))

for k in range(0, n):
    if b[k] == 1:
        l.append(k+1)

print(len(l))
for m in l:
    print(m)

Submission status: Accepted

Solution code:
N = int(input())
a = [int(x) for x in input().split()]
ans = []
li = [0]*N
x = 0
for ind,i in enumerate(a[N//2:]):
    if(i==1):
        ans.append(ind+1+N//2)
        li[ind+N//2] = 1
for ind,i in enumerate(a[:N//2][::-1]):
    n = N//2-ind
    if(sum(li[n-1::n])%2!=i):
        li[n-1]=1
        ans.append(n)
ans.sort()
print(len(ans))
if(len(ans)!=0):
    print(*ans)

Submission status: Accepted

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



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

ans =[]
#半分までは確定
fs = N // 2
for i in reversed(range(1, N + 1)):
    d_index = i * 2
    current_sum = 0
    while d_index <= N:
        if dps[d_index]:
            current_sum += 1
        d_index += i

    if current_sum % 2 == A[i-1]:
        dps[i] = False
    else:
        dps[i] = True


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


print(len(ans))
if len(ans) != 0:
    print(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
N = int(input())
x = [0]*N
aList = [int(x) for x in input().split()]

for i in range(N,0,-1):
    a = aList[i-1]
    b = 2
    c = 0
    while (i*b) - 1 < N:
        if x[(i*b)-1] == 1:
            c += 1
        b+=1
    x[i-1] = int(c%2==0 if a == 1 else c%2==1)

# output
print(sum(x))
for i,y in enumerate(x):
    if y == 1:
        print(i+1, end=' ')

Submission status: Accepted

Solution code:
N=int(input())
A=[0]+list(map(int,input().split()))
B=[0 for i in range(N+1)]
ans=[]
for i in range(1,N+1):
    n=N+1-i
    cnt=0
    
    for j in range(1,2*10**5+1):
        #print(n,n*j)
        if n*j>N:
            break
        else:
            if B[n*j]==1:
                cnt+=1
    if cnt%2!=A[n]%2:
        B[n]=1
        ans.append(n)
ans.sort()
print(len(ans))
print(*ans)
#print(A)
#print(B)

Submission status: Accepted

Solution code:
M=0
N=int(input())
A=list(map(int,input().split()))
A.insert(0,0)
B=[]
D=[0 for i in range(N+1)]
for i in range(N):
  i=N-i
  su=0
  for j in range(i+i,N+1,i):
    su=su^D[j]
  if su!=A[i]:
    B.append(str(i))
    M=M+1
    D[i]=1
  

C=[]
for i in range(len(B)):
  i=len(B)-i-1
  C.append(B[i])
print(M)
print(" ".join(C))

Submission status: Accepted

Solution code:
N=int(input())
A=[0]+list(map(int,input().split()))
B=[0 for i in range(N+1)]
ans=[]
for i in range(1,N+1):
    #print(i)
    n=N+1-i
    cnt=0
    for j in range(1,N+1):
        #print(n,j*n)
        if j*n>N:
            break
        if B[j*n]==1:
            cnt+=1
    if A[n]%2!=cnt%2:
        B[n]=1
        ans.append(n)
print(len(ans))
ans.sort()
print(*ans)
#print(A)

Submission status: Accepted

Solution code:
N=int(input())
A=[0]+list(map(int,input().split()))
B=[0 for i in range(N+1)]
ans=[]
for i in range(1,N+1)[::-1]:
    #print(i)
    cnt=0
    for j in range(1,N+1):
        #print(i,j)
        if j*i>N:
            break
        if B[j*i]==1:
            cnt+=1
    if A[i]%2!=cnt%2:
        B[i]=1
        ans.append(i)
print(len(ans))
ans.sort()
print(*ans)
#print(A)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

for i in range(n, 0, -1):
    for j in range(i, n + 1, i):
        b[i] ^= b[j]
    b[i] ^= a[i]

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

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
l1=[0 for i in range(n)]
for i in range(1,1+(n+1)//2):
  if l[-i]==1:
    l1[-i]=1
  else:
    pass
for i in range((n+1)//2-1,-1,-1):
  s=0
  for j in range(2,n//(1+i)+1):
    if l1[(i+1)*j-1]==1:
      s+=1
  if s%2==1:
    if l[i]==0:
      l1[i]=1
  else:
    if l[i]==1:
      l1[i]=1
l2=[]
s=0
for i in range(n):
  if l1[i]==1:
    s+=1
    l2.append(str(i+1))
print(s)
print(" ".join(l2))

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) :
    num = i+1
    cnt = 0
    for j in range(i+num,N,num) :
        cnt += B[j]
    if A[i] == 0 and cnt % 2 == 1 :
        B[i] = 1
    elif A[i] == 1 and cnt % 2 == 0 :
        B[i] = 1
print(sum(B))
for i,b in enumerate(B) :
    if b == 1 :
        print(i+1)

Submission status: Accepted

Solution code:
import math
N = int(input())
a = list(map(int, input().split()))
b = [0 for i in range(N + 1)]
for i in range(N, N // 2, -1):
    b[i] = a[i - 1]
for i in range(N // 2, 0, -1):
    bi = a[i - 1]
    for j in range(2, N // i + 1):
        bi = bi ^ b[i * j]
    b[i] = bi
print(sum(b))
for i, j in enumerate(b):
    if j == 1:
        print(i, end = ' ')

Submission status: Accepted

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

a = [0] + a
b = [0 for i in range(N+1)]
i = N
while i > 0:
    s = sum(b[i::i])
    if a[i] != s % 2:
        b[i] = 1
    i -= 1

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

Submission status: Accepted

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

l = [0]*N
p = []
for i in range(N-1, -1, -1):
    m = sum(l[i::i+1])%2
    if A[i] == m:
        continue
    l[i] = 1
    p.append(i)

print(len(p))
for p_i in p:
    print(p_i+1)

Submission status: Accepted

Solution code:
import math

anser=0
count=0
n  = int(input())
a = list(map(int, input().split()))
data  = []
result =[]
# for i in a[:math.floor(n/2-1):-1]:
# 	data.append(i)
# print(data)	
for i in range(n,0, -1):
	try:
		for s in range (2,math.floor(n/(i)+1)):
			count += data[-i*(s-1)]
	except IndexError:
		count = 0 
	data.append((count+a[i-1])%2)
	anser+=(count+a[i-1])%2
	count=0


print(anser)
if anser!=0:
	for i ,j in enumerate(data[::-1]):
		if j ==1:
			result.append(i+1)
	print(' '.join(list(map(str, result))))

Submission status: Accepted

Solution code:
N = int(input())
a = [0]+list(map(int, input().split()))
box = [None]+[0]*(N)
cnt = 0
   
for i in range(N, 0, -1):
    mult = [j for j in range(i,N+1,i)]
    sm = 0
    for m in mult:
        if box[m]:
            sm += 1
    if sm%2 != a[i]:
        box[i] = 1
        cnt += 1
        #print(box)
print(cnt)        
print(" ".join(map(str,[i for i,b in enumerate(box) if b])))

Submission status: Accepted

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

for i in range(N-1,-1,-1):
  a = A[i]
  for j in range(i+1,N+1,i+1):
    if j in ans:
      a += 1
  if a % 2:
    ans.add(i+1)
print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
##https://atcoder.jp/contests/abc134/submissions/6482430
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    A = [0] + list(int(i) for i in input().split())
    for i in range(n//2,0,-1):
        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(map(int, input().split()))
a.insert(0, 0)

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

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

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

Submission status: Accepted

Solution code:
N = int(input())

a = [0]

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

result = [0] * (N+1)
numbers = []

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

    for j in range(2*i, N+1, i):
        sum += result[j]

    if (a[i] - sum) % 2 == 0:
        result[i] = 0
    else:
        result[i] = 1
        numbers.append(i)

print(len(numbers))

for number in numbers:
    print(number, end=" ")

Submission status: Accepted

Solution code:
n = int(input())
A = [int(s) for s in input().split()]
cen = n //2
ANS = [0]*(cen)
A_p = A[cen:n]
ANS = ANS + A_p

for i in range(cen):
    part_sum = sum(ANS[cen-i-1::cen-i])
    dot = part_sum % 2
    if dot == A[cen-i-1]:
        pass
    else:
        ANS[cen-i-1] = 1

sum_ans = sum(ANS)
print(sum_ans)
if sum_ans == 0:
    pass
else:
    B = []
    for i in range(n):
        if ANS[i] != 0:
            B.append(str (i+1))
        else:
            pass
    B =" ".join(B)
    print(B)