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 = [int(x) for x in input().split()]
B = [0] * n

for i in reversed(range(n)):
    if i + 1 > n // 2:
        B[i] = A[i]
        # iの倍数が書かれた箱に入っているボールの個数はOK
    else:
        # iの倍数が書かれた箱に入っているボールの個数
        c = n // (i+1)
        s = 0
        for j in range(c):
            s += B[(i+1)*(j+1)-1]
        if s % 2 == A[i]:
            continue
        else:
            B[i] = 1

ans = sum(B)
print(ans)
count = 0
for i in range(len(B)):
    if B[i] == 1:
        count += 1
        if count == ans:
            print(i + 1)
        else:
            print(i + 1, end=' ')

# 欲しい出力を如何に高速に得るかも重要

Submission status: Accepted

Solution code:
n = int(input())
A = [int(x) for x in input().split()]
B = [0] * n

for i in reversed(range(n)):
    if i + 1 > n // 2:
        B[i] = A[i]
        # iの倍数が書かれた箱に入っているボールの個数はOK
    else:
        # iの倍数が書かれた箱に入っているボールの個数
        c = n // (i+1)
        s = 0
        for j in range(c):
            s += B[(i+1)*(j+1)-1]
        if s % 2 == A[i]:
            continue
        else:
            B[i] = 1

ans = sum(B)
print(ans)
count = 0
for i in range(len(B)):
    if B[i] == 1:
        count += 1
        if count == sum:
            print(i + 1)
        else:
            print(i + 1, end=' ')

Submission status: Accepted

Solution code:
n = int(input())
AL = [0] + list(map(int, input().split()))
ball_plus_list = [0]*(n+1)
for i in range(n, 0, -1):
    sum_ball = 0
    for j in range(2, n//i + 1):
        sum_ball += ball_plus_list[i*j]
    if sum_ball%2 != AL[i]:
        ball_plus_list[i] = 1

ans = []
for i, ball_exist in enumerate(ball_plus_list):
    if ball_exist == 1:
        ans.append(str(i))
print(len(ans))
print(" ".join(ans))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b = [] #i=n-1からi=0まで逆向き

for i in reversed(range(n)):
  if i>=n//2:
    b.append(a[i])
  else:
    #k＊番号の箱の合計、番号はi+1
    temp = [b[n-k*(i+1)] for k in range(2,n//(i+1)+1)]
    b.append((sum(temp)-a[i])%2)

b.reverse()
print(b.count(1))
for i in range(n):
  if b[i]==1:
    print(i+1, end=" ")

Submission status: Accepted

Solution code:
N = int(input())
a_list = list(map(int, input().split()))
n_dict = {i:0 for i in range(1, N+1)}

for i in range(N, 0, -1):
    j = i
    a = a_list[j-1]
    temp_a = 0
    while j <= N:
        temp_a += n_dict[j]
        j += i
    if temp_a % 2 == a:
        pass
    else:
        n_dict[i] = 1

ans_num = list(n_dict.values())
ans_num = ans_num.count(1)
print(ans_num)

ans_str = ""
for i in range(1, N+1):
    if n_dict[i] == 1:
        if ans_str == "":
            ans_str = str(i)
        else:
            ans_str += " "+str(i)
if ans_str == "":
    pass
else:
    print(ans_str)

Submission status: Accepted

Solution code:
n=int(input())
a=[-1]+[int(x) for x in input().split()]
b=[-1]+[0]*n
for i in range(n,0,-1):
  #print(b[::i][1:],a[::i][1:])
  if sum(b[::i][1:])%2!=a[i]:
    b[i]=int(not b[i])
    #print(b[::i][1:],a[::i][1:])
    if sum(b[::i][1:])%2!=a[i]:
      print(-1)
      exit()

ans=[n for n,x in enumerate(b) if x==1]
print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
boxes = [0] * N
for i in reversed(range(N)):  # i from N-1 to 0
    boxes[i] = (2 + a[i] - sum(boxes[i::i + 1]) % 2) % 2

ansCount = 0
ansIndices = []
for idx, content in enumerate(boxes):
    if content:
        ansCount += 1
        ansIndices.append(idx + 1)

print(ansCount)
if ansCount > 0:
    print(" ".join(map(str, ansIndices)))

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):
  x=sum(b[2*i::i])
  
  if x%2!=a[i]:
    b[i]=1
    
print(sum(b))
for i in range(1, N+1):
  if b[i]==1:
    print(str(int(i)), end=' ')

Submission status: Accepted

Solution code:
N = int(input())
a = [0] + list(map(int, input().split()))
ans = [0] * (N + 1)
an = []
for i in range(N, 0, -1):
	if sum(ans[i * 2 :: i]) % 2 != a[i]:
		ans[i] = 1
		an.append(i)
print(len(an))
Ans = [str(x) for x in an]
print(' '.join(Ans))

Submission status: Accepted

Solution code:
#import numpy as np
N = int(input())
a = [0]+list(map(int,input().split()))
ans = [0]*(N+1)
an = []
for i in range(N,0,-1):
  c =0
  c = sum(ans[2*i::i])
  if c%2!=a[i]:
    ans[i]=1
    an.append(i)
print(len(an))
for i in range(len(an)):
  print(an[i],end=" ")

Submission status: Accepted

Solution code:
#import numpy as np
N = int(input())
a = [0]+list(map(int,input().split()))
ans = [0]*(N+1)
an = []
for i in range(N,0,-1):
  c =0
  b = [i*j for j in range(2,N//i+1)]
  for j in b:
    c +=ans[j]
  c = c%2
  if c!=a[i]:
    ans[i]=1
    an.append(i)
print(len(an))
for i in range(len(an)):
  print(an[i],end=" ")

Submission status: Accepted

Solution code:
#import numpy as np
N = int(input())
a = [0]+list(map(int,input().split()))
ans = [0]*(N+1)
an = []
for i in range(N,0,-1):
  c =0
  b = [i*j for j in range(2,N//i+1)]
  for j in b:
    c +=ans[j]
  c = c%2
  if c!=a[i]:
    ans[i]=1
    an.append(i)
print(len(an))
for i in range(len(an)):
  print(an[i],end=" ")

Submission status: Accepted

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

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

    count = 0
    ball = [0] * (N+1)

    for i in range(N, 0, -1):
        tmp = 0
        for j in range(i*2, N+1, i):
            tmp += ball[j]
        if tmp%2 != a[i-1]:
            ball[i] = 1
            count += 1
    
    print(count)
    if count > 0:
        for i in range(1, N+1):
            if ball[i] == 1:
                print(i, end=" ")
        print()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#18:45
n = int(input())
a = list(map(int,input().split()))
b = [0 for _ in range(n)]
for i in range(n,0,-1):
  tmp = 0
  here = i
  while True:
    try:
      tmp ^= b[here-1]
      here += i
    except:
      tmp ^= a[i-1]
      break
  if tmp == 1:
    b[i-1] = 1
print(sum(b))
c = []
for i in range(n):
  if b[i] == 1:
    c.append(i+1)
print(' '.join(list(map(str,c))))

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 j in range(1, n+1):
  if a[j] == 1:
    print(j)

Submission status: Accepted

Solution code:
n,a=open(0);n=int(n);b=[0]*-~n
for x in range(n,0,-1):b[x]=(sum(b[x::x])+int(a[x*2-2]))%2
print(sum(b));print(*[i+1for i in range(n)if b[i+1]])

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
for x in range(n-1,0,-1):a[x-1]=(sum(a[x*2-1::x])+a[x-1])%2
print(a.count(1));print(*[i+1 for i in range(n)if a[i]],end=" ")

Submission status: Accepted

Solution code:
n,*a = map(int,open(0).read().split())
b = [0]*(n+1)
for x in range(n,0,-1):
	b[x] = (sum(b[x::x])+a[x-1])%2
print(b.count(1))
for i in range(n+1):
	if b[i]:
		print(i,end=" ")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = [int(x) for x in input().split()]
solls = np.zeros(N+1)
A.insert(0,0)
solls[N//2+1:] = A[N//2+1:]

for i in range(N//2,0,-1):
    s = 0
    for j in range(2*i,N+1,i):
        s = s+solls[j]
    if (s%2 == 0)and(A[i] == 1):
        solls[i] = 1
    if (s%2 == 1)and(A[i] == 0):
        solls[i] = 1

s = 0
ls = []
for i in range(N+1):
    if solls[i] == 1:
        ls.append(i)
        s = s+1

print(s)
print(*ls)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = [int(i) for i in input().split(" ")]
b = [0 for i in range(n//2)] + a[n//2:]
for i in range(n//2-1, -1, -1):
    if sum(b[i::i+1])%2 != a[i]:
        b[i] = 1
te = sum(b)
if te == 0:
    print(0)
else:
    print(te)
    print(" ".join(map(str, np.where(np.array(b)==1)[0]+1)))

Submission status: Accepted

Solution code:
n = int(input())
a = input()
r = [None] * (n + 1)
for i in range(n, 0, -1):
    r[i] = (ord(a[2 * i - 2]) + sum(r[i * 2::i])) % 2
print(r.count(1))
print(*(i for i, x in enumerate(r) if x))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b = [0 for i in range(n)]
	
for i in range(n)[::-1]:
	sm = 0
	for j in range(n):
		if (j + 1) * (i + 1) <= n:
			sm += b[(j + 1) * (i + 1) - 1]
		else:
			break
	if sm % 2 != a[i]:
		b[i] += 1

ans = [str(i + 1) for i, bb in enumerate(b) if bb == 1]
nans = len(ans)
print(nans)
if nans != 0:
	print(' '.join(ans))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(n // 2)] + a[n // 2:]
for i in range(n // 2 - 1, -1, -1):
    b[i] = abs(a[i] - sum(b[i::i + 1]) % 2)
print(sum(b))
print(*([i + 1 for i, bi in enumerate(b) if bi > 0]))

Submission status: Accepted

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

count = 0
result = []
x=[0]*n
for i in xrange(n,0,-1):
    total = 0
    for j in xrange(i,n+1,i):
        total += x[j-1]
    if  total % 2 != a[i-1]:
        x[i-1]=1
        result.append(i)
    else:
        pass
print len(result)
print ' '.join(map(str,result))

Submission status: Accepted

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

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

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

    print(res.count(1))
    if res.count(1) != 0:
        print(*[i for i,r in enumerate(res) if r == 1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

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

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

    print(res.count(1))
    if res.count(1) != 0:
        print(*[i for i,r in enumerate(res) if r == 1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [None] + [int(i) for i in input().split()]
ans = []
choose = [0] * (N+1)

for n in range(N, 0, -1):
  x = sum(choose[2*n::n])
  if x % 2 == A[n]:
    continue
  choose[n] += 1  
  ans.append(str(n))

print(len(ans))
print(' '.join(ans))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
b = [0 for _ in range(len(a))]

ans = ""
anscount = 0
for i in range(n-1, -1, -1):
  ai = a[i]
  j = i + 1
  while i < n:
    if b[i]:
      ai ^= 1
    i += j
    b[j-1] = ai
res = []
for i, one in enumerate(b):
  if one==1:
    res.append(i+1)
print(len(res))
print(*res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = [0] * N
C = []
for i in range(N,0,-1):
  parity = 0
  j = 2
  while(i * j <= N):
    parity += B[i * j - 1]
    j += 1
  B[i - 1] = (A[i - 1] - parity) % 2
print(sum(B))
for i in range(N):
  if(B[i] == 1):
    C.append(str(i + 1))
if(C != []):
  print(" ".join(C))

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


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
n=int(input())
A=[0]+list(map(int, input().split()))
B=[0]*(n+1)
B[n//2+1:]=A[n//2+1:]
for i in range(n//2, 0, -1):
  B[i]=(sum([B[j] for j in range(2*i, n+1, i)])+A[i])&1
res=[]
for i in range(n+1):
  if B[i]==1:
    res.append(i)
print(len(res))
if res:
  print(*res)

Submission status: Accepted

Solution code:
N = int(input())
S = list(map(int, input().split()))
 
final_list = [0 for _ in range(N)]
ans_list = []
for n in reversed(range(N)):
    i = n+1
    quot = N // i
    rem = S[n]
    count = 0
    for j in range(1, quot+1):
        tmp_a = final_list[i*j -1]
        count ^= tmp_a
    if rem != count:
        final_list[n] = 1 
        ans_list.append(i)
        
print(len(ans_list))
print(' '.join(map(str, ans_list)))

Submission status: Accepted

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

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

m = sum(b_arr)
print(m)
if m:
    ans = []
    for i in range(1,n+1):
        if b_arr[i]:
            ans.append(i)
    print(*ans)

Submission status: Accepted

Solution code:
N = int(input())
par = []
for i in range(1,N+1):
    par.append([j for j in range(i,N+1,i)])
A = [int(i) for i in input().split()]
List = [0 for i in range(N)]
for i in range(N-1,-1,-1):
    tmp = 0
    for j in par[i]:
        tmp += List[j-1]
    if A[i] == 1 and tmp%2==0:
        List[i] = 1
    elif A[i] == 0 and tmp%2==1:
        List[i] = 1
print(List.count(1))
ans = []
for i in range(len(List)):
    if List[i]==1:
        ans.append(i+1)
print(*ans)

Submission status: Accepted

Solution code:
from functools import reduce
add = lambda a, b: a+b

N = int(input())
a = [0] + [int(x) for x in input().split()]
balls = [0]*(N+1)

for i in range(N, 0, -1):
  if sum([balls[j] for j in range(i, N+1, i)]) % 2 != a[i]:
    balls[i] += 1

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

if len(ans) != 0:
  print(" ".join([str(a) for a in ans]))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.insert(0,0)
B = [0 for _ in range(N+1)]
B[N//2+1:] = A[N//2+1:]
for i in range(N//2,0,-1):
    tot = 0
    for j in range(2*i,N+1,i):
        tot += B[j]
    B[i] = (A[i]+tot)%2
C = []
M = 0
for i in range(1,N+1):
    if B[i]==1:
        M += 1
        C.append(i)
print(M)
if M!=0:
    print(*C)

Submission status: Accepted

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

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, ele in enumerate(res):
        if ele:
            ans.append(i)
    print(*ans)

Submission status: Accepted

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

print(count)
[print(i+1,end=" ") for i,x in enumerate(ans) if x==1]

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
w=[0]*n
for i in range(n-1,-1,-1):
    cnt=0
    for j in range(i,n,i+1):
        cnt+=w[j]
    if cnt%2!=a[i]:
        w[i]=1
print(w.count(1))
if w.count(1):
    ans=[]
    for i in range(n):
        if w[i]==1:
            ans.append(i+1)
    print(*ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
t=[0]*n
p=[]
g=0
for i in range(n-1,-1,-1):
    if sum(t[i::i+1])%2!=a[i]:
        t[i]=1
        p.append(i+1)
        g+=1
print(g)
print(*p[::-1])

Submission status: Accepted

Solution code:
n = int(input())

a = list(map(int, input().split()))
box = [0]*n
for i in range(n,0,-1):
    sum_box = 0
    for j in range(i,n+1,i):
        sum_box+=box[j-1]
    if sum_box%2!=a[i-1]:
        box[i-1]+=1
 
print(sum(box))
if sum(box):
    ans = []
    for i, x in enumerate(box):
        if x:
            ans.append(i+1)
    print(*ans)

Submission status: Accepted

Solution code:
import sys
import math
from copy import deepcopy
from collections import deque
sys.setrecursionlimit(20000000)


def main():
    N = int(input())
    boxes = [0] * (N+1)
    ans_boxes = [0]
    [ans_boxes.append(x) for x in list(map(int, input().split()))]

    count = 0
    ans = []

    def judge(n):
        s = 0

        nn = n
        while nn < len(boxes):
            s += boxes[nn]
            nn += n

        if s % 2 == ans_boxes[i]:
            return True
        else:
            return False

    for i in reversed(range(1, len(boxes))):
        if judge(i):
            continue

        else:
            count += 1
            ans.append(i)
            boxes[i] += 1
            if judge(i):
                pass
            else:
                print(-1)
                sys.exit()

    print(count)
    if ans:
        print(*ans, sep=' ')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
listA=(input().split())
list1=[0 for i in range(n)]
list2=[]
numOfBox=0
#考えるべきボールの数の合計
for i in range(n,0,-1):#n,n-1,...1って感じです
    #print(i)
    count=1
    s=0
    while i*count<=n:
        s+=list1[i*count-1]
        count+=1
    #print(s)
    if s%2!=int(listA[i-1]):
        list1[i-1]+=1
        numOfBox+=1
        list2.append(i)
#print(list1)
print(numOfBox)
for i in range(len(list2)):
    print(list2[i],end=" ")

Submission status: Accepted

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

b = [0]*(N+1)
for i in range(N,0,-1):
    if N//i == 1:
        b[i] = a[i]
    else:
        tmp = a[i]
        loop = N//i
        index = i*loop
        for j in range(loop):
            if j == loop-1: # end
                b[i] = tmp
            else:
                tmp = (tmp+b[index])%2
                index -= i
print(sum(b))
for i in range(1,N+1):
    if b[i] == 1:
        print(i, end=" ")

Submission status: Accepted

Solution code:
n = int(input())
*a, = map(int,input().split())
box = [0]*n
for i in range(n,0,-1):
    sum_box = 0
    for j in range(i,n+1,i):
        sum_box+=box[j-1]
    if sum_box%2!=a[i-1]:
        box[i-1]+=1

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
arr = na()
s = sum(arr)
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, ele in enumerate(res):
        if ele:
            ans.append(i)
    print(*ans)

Submission status: Accepted

Solution code:

n = int(input())
arr = [int(x) for x in input().split()]
balls = {}
result = []
reslen = 0

for i in range(n, n // 2, -1):
  if arr[i - 1] == 1:
    balls[i - 1] = 1
    result.append(str(i))
    reslen += 1
  else:
    balls[i - 1] = 0

for i in range(n // 2, 0, -1):
  s = sum([balls[i * m - 1] for m in range(2, n // i + 1)])
  if arr[i - 1] == 1:
    if (s % 2) == 1:
      balls[i - 1] = 0
    else:
      balls[i - 1] = 1
      result.append(str(i))
      reslen += 1
  if arr[i - 1] == 0:
    if (s % 2) == 0:
      balls[i - 1] = 0
    else:
      balls[i - 1] = 1
      result.append(str(i))
      reslen += 1

print(reslen)
if reslen != 0:
  print(' '.join(result))

Submission status: Accepted

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    n,*a=map(int,open(0).read().split())
    dp=deepcopy(a)
    dp[:n//2]=[0]*(n//2)
    for i in reversed(range(n//2)):
        if sum(dp[j] for j in range(i,n,i+1))%2!=a[i]:
            dp[i]=1
    #print(dp)
    d=[k+1 for k,v in enumerate(dp)if v==1]
    print(len(d))
    print(*d)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    n,*a=map(int,open(0).read().split())
    dp=deepcopy(a)
    dp[:n//2]=[0]*(n//2)
    for i in reversed(range(n//2)):
        if sum(dp[j] for j in range(i,n,i+1))%2!=a[i]:
            dp[i]=1
    #print(dp)
    d=[k+1 for k,v in enumerate(dp)if v==1]
    print(len(d))
    print(*d)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    A=LI()
    B = [(i,a) for i,a in enumerate(A,start = 1)][::-1]

    #sigma(1/i) = O(log N)
    balls = set()
    for i,a in B:
        cnt = 0
        for j in range(N+1):
            k = i*j
            if k > N:
                break
            elif k in balls:
                cnt += 1
        if cnt%2 != a:
            balls.add(i)
    print(len(balls))
    print(*balls,sep="\n")

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for i in range(N):
    ind = N-i
    val = 0
    j=2
    while ind*j<=N:
        val += b[ind*j]
        j+=1
    if val%2 != a[ind]:
        M+=1
        b[ind]=1
print(M)
if M!=0:
    for i in range(1,N+1):
        if b[i]==1:
            M-=1
            if M!=0:
                print(i,end=' ')
            else:
                print(i)

Submission status: Accepted

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

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

for i in range(N):
    ind = N-i
    val = 0
    j=2
    while ind*j<=N:
        val += b[ind*j]
        j+=1
    if val%2 != a[ind]:
        M+=1
        b[ind]=1
print(M)
if M!=0:
    for i in range(1,N+1):
        if b[i]==1:
            if M!=1:
                print(i,end=' ')
            else:
                print(i)

Submission status: Accepted

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

Submission status: Accepted

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

info = [0] * (n+1)

for i in range(0,n):
    count = 0
    for j in range(2,n//(n-i) + 1):
        count += info[(n-i)*j]
    if count % 2 != a[n-i]:
        info[n-i] = 1

ans = []

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

print(len(ans))
print(" ".join(map(str,ans)))

Submission status: Accepted

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

bs = nums.copy()
res = []

for i in range(n // 2, 0, -1):
    val = 0
    for j in range(1, n // i + 1):
        if i * j <= n:
            val += bs[i * j - 1]
    bs[i - 1] = val % 2
for i in range(n):
    if bs[i] > 0:
        res.append(i + 1)
m = sum(bs)
print(m)
if m > 0:
    print(' '.join(map(str, res)))

Submission status: Accepted

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

d = [0] * (n + 1)

for j in range(n):
    i = n - j
    if n // i == 1:
        d[i] = a_list[j]
    else:
        c = 0
        for k in range(n // i, 1, -1):
            c += d[k * i]
        d[i] = (c + a_list[j]) % 2

counter = 0
res = []

for k in range(n):
    if d[k + 1] == 1:
        counter += 1
        res.append(k + 1)

print(counter)
if len(res) > 0:
    print(*res)

Submission status: Accepted

Solution code:
N = int(input())
flag = [-1]*N
ans = []
lst = list(map(int, input().split()))
for i in range(N-1, -1, -1):
    cnt = 0
    for j in range(i, N, i+1):
        if j == i:
            continue
        else:
            if flag[j] == 1:
                cnt += 1
    if (lst[i]+cnt)%2 == 0:
        flag[i] = 0
    else:
        flag[i] = 1
        ans.append(i+1)
num = len(ans)
if num == 0:
    print(0)
else:
    print(num)
    print(*ans)

Submission status: Accepted

Solution code:
# ttps://atcoder.jp/contests/abc134/submissions/6460745
n = int(input())
a = list(map(int, input().split()))
b = [None]*n

for i in range(n,0,-1):     #0はrangeの範囲外
    b[i-1] = a[i-1]
    k = 2*i                 #kはiの倍数
    while k <= n:
        b[i-1] ^= b[k-1]    #XOR 1^1=0^0=0,1^0=0^1=1
                            #ビット演算子
        k += i              #2i,3i,...と調べる

M = sum(b)
print(M)
if M>0:
    print(' '.join( [str(j+1) for j,b_ in enumerate(b) if b_==1] ))
        #b=1を抽出、index+1を" "で連結

Submission status: Accepted

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

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

print(ans)
for bb in b:
    print(bb, end=" ")

Submission status: Accepted

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

n = int(input())
a_lst = list(map(int, input().split()))
b_lst = [0]*n

def multiple_i(i, n):
        lst = []
        j = 2
        while(1):
            if i*j <= n:
                lst += [i*j]
                j += 1
            else:
                break
        return lst

for i in range(1, n+1):
    r = a_lst[-i]
    if not n+1-i > n / 2:
        mul_lst = multiple_i(n+1-i, n)
        ball = 0
        for mul in mul_lst:
            if b_lst[mul - 1] == 1:
                ball += 1
        if not ball % 2 == r:
            b_lst[-i] = 1
    else:
        if r == 1:
            b_lst[-i] = 1

m = 0
ans_lst = []
for i in range(n):
    if b_lst[i] == 1:
        m += 1
        ans_lst += [i + 1]

print(m)
for i in range(m):
    print(ans_lst[i], end=" ")

Submission status: Accepted

Solution code:
n = int(input())
L = list(map(int,input().split()))
dp = [0]*n
if n%2 == 0:
  for i in range(n//2):
    if L[n-i-1] == 1:
      dp[n-i-1] += 1
  for i in range(n//2,0,-1):
    cur = 0
    for j in range(n//i):
      cur += dp[i*(j+1)-1]
    if cur%2 != L[i-1]%2:
      dp[i-1] += 1
else:
  for i in range(n//2+1):
    if L[n-i-1] == 1:
      dp[n-i-1] += 1
  for i in range(n//2,0,-1):
    cur = 0
    for j in range(n//i):
      cur += dp[i*(j+1)-1]
    if cur%2 != L[i-1]%2:
      dp[i-1] += 1
if sum(dp) == 0:
  print(0)
else:
  T = []
  for i in range(n):
    if dp[i] == 1:
      T.append(i+1)
  print(len(T))
  print(' '.join(map(str, T)))