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(_) for _ in input().split()]
b = [0] * n
res = []
m = 0
for i in range(n//2,n):
    if a[i] == 1:
        res.append(i+1)
        b[i] = 1
        m += 1
for i in range(n//2):
    k = n//2-i
    cnt = 0
    for j in range(2*k-1,n,k):
        if b[j] == 1:
            cnt = (cnt+1)%2
    if cnt != a[k-1]:
        res.append(k)
        b[k-1] = 1
        m += 1 
if m == 0:
    print(0)
else:
    print(m)
    for i in range(m):
        if i != 0:
            print(' ',end='')
        print(res[i],end='',)
    print()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int,input().split()))
    boxes = [0] * N

    count = 0
    printlist = []
    for i in range(N//2,N):
        boxes[i] = A[i]
        if A[i] == 1:
            count += 1
            printlist.append(i)
            #print('append i:',i)
    for i in range(N//2-1,-1,-1):
        s = A[i]
        #print('i=',i)
        for j in range(2,N//(i+1)+1):
            #print('idx=',(i+1)*j - 1)
            s ^= boxes[(i+1)*j - 1]
        boxes[i] = s
        if s == 1:
            count += 1
            printlist.append(i)
            #print('append i:',i)

    import sys
    print(count)
    for i in printlist:
        sys.stdout.write(str(i+1))
        sys.stdout.write(' ')
    print()

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))
b = [-1] * N
nfi = N // 2
for i in range(nfi,N):
    b[i] = a[i]
for j in range(nfi-1,-1,-1):
    bn = b[j::j+1][1:]
    bnsum = sum(bn)
    if a[j] == 1:
        if bnsum%2==1:b[j] = 0
        else:b[j] = 1
    else:
        if bnsum%2==0:b[j] = 0
        else:b[j] = 1        
dl = []
for k in range(N):
    if b[k] == 1:
        dl.append(k+1)
if sum(b) == 0:
    print(0)
else:
    print(sum(b))
    print(*dl)

Submission status: Accepted

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

b=[-1]*N
b[N-1]=a[N-1]
for i in range(N-1)[::-1]: #N=4なら 2,1,0
    sum_count = N // (i+1)
    if sum_count==1:
        b[i]=a[i]
    else:
        sum1=0
        for j in range(sum_count-1):
            sum1 = sum1 + b[(i+1)*(j+2)-1]
        sum1 = sum1 % 2
        b[i]=(a[i]+ sum1)%2

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
r = [None] * (n + 1)
for i in range(n, 0, -1):
    r[i] = (a[i - 1] + 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:
import sys
input = sys.stdin.readline

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

answer = []
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
    answer.append(str(n))

print(len(answer))
print(' '.join(answer))

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int,input().split()))
u = []
m = n
c = [0]*n
b = 0
count = 0
for i in range(2,n+1):
    while(m>n//i):
        b=0
        for j in range(1,i):
            b = b^l[m*j-1]
            #print(b,m*j)
        l[m-1] = b
        if(b):
            u.append(m)
            count += 1
        m -= 1
b = 0
for i in range(0,n):
    b = b^l[i]
if(b):
    u.append(m)
    count += 1
print(count)
if(u):
    print(*list(reversed(u)))

Submission status: Accepted

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

for i in range(n):
	# if n-i in yakusu(n):
		cnt=0
		for k in range(n//(n-i)):
			if b[(n-i)*(k+1)-1]==1:
				cnt+=1
		if cnt%2==a[n-i-1]:
			b[n-i-1]=0
		else:
			b[n-i-1]=1
	# else:
	# 	b[n-i-1]=a[n-i-1]
ans_1=0
ans_2=[]
for i in range(n):
	if b[i]==1:
		ans_1+=1
		ans_2.append(i+1)
print(ans_1)
print(*ans_2)

Submission status: Accepted

Solution code:
import os, sys, re, math

N = int(input())

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

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

for i in range(N,0,-1):
    temp_s = 0
    m = 2
    while m * i <= N:
        temp_s += memo[m*i]
        m += 1

    memo[i] = (temp_s % 2) ^ a[i-1]

ret = [i for i in range(1,N+1) if memo[i] == 1]
if len(ret) == 0:
    print(0)
else:
    print(len(ret))
    ret = list(map(str,ret))
    print(' '.join(ret))

Submission status: Accepted

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

for i in range(n, n//2, -1):
  if a[i-1]:
    c[i-1] = 1
for i in range(n//2, 1, -1):
  t = i
  tt = 0
  cnt = 1
  while t<=n:
    tt += c[t-1]
    cnt += 1
    t = i*cnt
  if (a[i-1]==1 and tt%2==0) or (a[i-1]==0 and tt%2==1):
    c[i-1] = 1

ttt = sum(c)
if (ttt%2==0 and a[0]==1) or (ttt%2==1 and a[0]==0):
  c[0] = 1
  ttt += 1
#print(c)
ans = []
for i in range(n):
  if c[i]:
    ans.append(i+1)
print(ttt)
if ttt:
  print(*ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [0] + list(map(int, input().split()))
ans = [0]*(n+1)
for i in range(n, n//2, -1) : ans[i] = a[i]
for i in range(n//2, 0, -1) :
    tmp = 0
    for j in range(i+i, n+1, i) : tmp += ans[j]
    ans[i] = (tmp+a[i])%2
print(sum(ans))
for i in range(1, n+1) : ans[i] *= i
print(" ".join(map(str, list(filter(lambda x:x!=0, ans)))))

Submission status: Accepted

Solution code:
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

def main():
    N = i2n()
    A = i2nn()
    X = [0] * N
    Y = [0] * N
    for i in range(N, 0, -1):
        t = (A[i-1] + X[i-1]) % 2
        if t > 0:
            Y[i-1] = 1
            divisors = make_divisors(i)
            for d in divisors:
                X[d-1] += t
    B = []
    for i, y in enumerate(Y):
        if y > 0:
            B.append(i+1)
    M = len(B)
    print(M)
    if M > 0:
        print(' '.join([str(b) for b in B]))

main()

Submission status: Accepted

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

shoki = N // 2
A.insert(0, -1)
N += 1
boxes = [0 for i in range(N)]
result = []

N -= 1
for i in range(N, shoki, -1):
    boxes[i] = A[i]
    if A[i] == 1:
        result.append(i)

for i in range(shoki, 0, -1):
    mul = 2
    val = i
    cnt = 0
    while val*mul <= N:
        if boxes[val*mul] == 1:
            cnt += 1
        mul += 1
    if A[i] == 0 and (cnt % 2) == 0:
        boxes[i] = 0
    elif A[i] == 0:
        boxes[i] = 1
        result.append(i)
    elif A[i] == 1 and (cnt % 2) == 0:
        boxes[i] = 1
        result.append(i)
    else:
        boxes[i] = 0
if result:
    print(str(len(result)))
    print(*result)
else:
    print("0")

Submission status: Accepted

Solution code:
n = int(input())


def divisor(n):  # 約数全列挙
    ans = [1, n]
    i = 2
    while i ** 2 <= n:
        if n % i == 0:
            ans.append(i)
            if i ** 2 < n:
                ans.append(n // i)
        i += 1
    ans.sort()
    return ans
a = list(map(int,input().split()))
ans = []
for num in range(n-1,-1,-1):
    if a[num] %2== 1:
        ans.append(num+1)
        q = divisor(num+1)
        for j in q:
            a[j-1] += 1

print(len(ans))
for i in ans:
    print(i,end=' ')

print()

Submission status: Accepted

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

ball = [False for _ in range(n)]

ans = []
for i, a in enumerate(reversed(box)):
    #print("{} {}".format(i,a))
    idx = n - 1 - i
    count_right = 0
    p = 2
    j = (idx + 1) * p
    #print("{}: {} <= {}".format(idx, j,n))
    while j <= n:
        #print("w {} {}".format(idx,n))
        if ball[j-1]:
            count_right += 1
        p+=1
        j = (idx + 1)  * p
    if a != 0:
        if (count_right % 2) != 0:
            ball[idx] = False
        else:
            ball[idx] = True
            ans.append(idx+1)
    else:
        if (count_right % 2) != 0:
            ball[idx] = True
            ans.append(idx+1)
        else:
            ball[idx] = False

ans_len = len(ans)
print(ans_len)
if (int(ans_len) == 0):
    pass #print('exit')
else:
    ans_s = ""
    for i, b in enumerate(ball):
        if b:
            if ans_s == "":
                ans_s = str(i+1)
            else:
                ans_s += " "
                ans_s += str(i+1)
    print(ans_s)
    #    if a != 0:
    #        ball[idx] = True

Submission status: Accepted

Solution code:
n=int(input())

A=[int(i) for i in input().split()]
Ans=[]
C=[False]*n
for i in reversed(range(n)):
  if A[i]==1:    
    if 2*(i+1)>n:
      Ans.append(i+1)
      C[i]=True
    else:
      c=0
      j=2
      while j*(i+1)<=n:
        if C[j*(i+1)-1]==True:
          c^=1
        j+=1
      if c==0:
        Ans.append(i+1)
        C[i]=True
        
  elif A[i]==0:    
    c=0
    j=2
    while j*(i+1)<=n:
      if C[j*(i+1)-1]==True:
        c^=1
      j+=1
    if c==1:
      Ans.append(i+1)
      C[i]=True
      
if len(Ans)==0:
  print(0)
else:
  print(len(Ans))
  Ans.sort()
  print(*Ans)

Submission status: Accepted

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

b = [0] * N
i = N-1
while i >= 0:
    for j in range(1, N//(i+1)):
        c[i] = c[i] - b[(j+1)*(i+1)-1]
    b[i] = c[i]%2
    i -= 1


count = 0
for i in range(N):
    e = sum(b[i::i+1])
    if e%2 != a[i] :
        print(-1)
        count =1
        break


if count == 0 :
    d = []

    print(b.count(1))

    for i in range(N):
        if b[i] ==1 :
            d.append(str(i+1))

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

Submission status: Accepted

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

for i in range(n):
    t = n - i - 1
    if i < n / 2:
        b[t] = a[t]
    else:
        to = 0
        j = 0
        for i in range(n // (t + 1)):
            to += b[(i + 1) * (t + 1) - 1]
        if to % 2 != a[t]:
            b[t] = 1

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(map(int,input().split()))
m=0
b=[0]*n
for i in reversed(range(n)):
    num=int(n/(i+1))
    #print("["+str(num)+"]")
    if num==1:
        if a[i]==1:
            b[i]=1
            m+=1
    else:
        sum=0
        for j in range(num):
            sum+=b[(i+1)*(j+1)-1]
        sum%=2
        if a[i]==1:
            b[i]=1-sum
            m+=1-sum
        else:
            b[i]=sum
            m+=sum
        
print(m)
if(m!=-1):
    for i in range(n):
        if b[i]!=0:
            print((i+1),end=" ")
        print("")

Submission status: Accepted

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

import math

if __name__ == '__main__':
    N = int(input())
    A = [int(c) for c in input().split()]
    R = [0 for i in range(N)]
    M = 0

    for i in range(N-1, -1, -1):
        # print('i={}'.format(i))
        start = i
        sum = 0
        for j in range(start, N, i + 1):
            # print('  j={}'.format(j))
            sum += R[j]
        # print(sum)
        # print(A[i])
        if sum % 2 != A[i]:
            R[i] = 1
            M += 1

    # print(R)

    print(M)
    if M != 0:
        for i in range(N):
            if R[i] == 1:
                print(i+1, end=' ')

Submission status: Accepted

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

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

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

s = sum(ball)
print(s)
if s != 0:
    out = str(ball.index(1) + 1)
    for i in range(int(out), N):
        if ball[i] == 1: out += ' ' + str(i+1)
    print(out)

Submission status: Accepted

Solution code:
n=int(input())
lst=list(map(int,input().split()))
ball=[0 for x in range(n)]
for i in range(n):
  idx=n-1-i
  if idx==n-1:
    ball[idx]=lst[idx]
  else:
    num=int(n/(idx+1)-1)
    sum_ball=0
    for j in range(2,num+2):
      sum_ball+=ball[(idx+1)*j-1]
    if sum_ball%2==lst[idx]:
      continue
    else:
      ball[idx]=1
      
indexes=[i+1 for i,x in enumerate(ball) if x==1]
if len(indexes):
  print(len(indexes))
  for i,x in enumerate(indexes):
    if i!=0:
      print(" ",end="")
      print(x,end="")
    else:
      print(x,end='')
  print()
else:
  print(0)

Submission status: Accepted

Solution code:
import sys
N=input()
A=map(int, sys.stdin.readline().split())


ans=[ 0 for i in range(N) ]
V=[ 0 for i in range(N) ]

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

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


cnt=sum(ans)
if cnt==0:
	print 0
	quit()
else:
	print cnt
	for i,x in enumerate(ans):
		if x==1:
			print i+1

Submission status: Accepted

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

if N % 2 == 0:
    k = N // 2
    x = [0] * k + a[k:]
    start = k
else:
    k = (N + 1) // 2
    x = [0] * (k - 1) + a[k - 1:]
    start = k - 1

for i in range(start, 0, -1):
    x[i - 1] = (sum(x[2 * i - 1::i]) + a[i - 1]) % 2

M = 0
b = []
for i in range(N):
    if x[i] == 1:
        M += 1
        b.append(str(i + 1))
print(M)
print(' '.join(b))

Submission status: Accepted

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

res = [0 for i in range(N)]
for i in range(N, 0, -1):
    othors_idxs = [(j+1)*i-1 for j in range(int(N/i)) if j != 0]
    othors = [res[idx] for idx in othors_idxs]
    if sum(othors + [1]) % 2 == A[i-1]:
        res[i-1] = 1

ans = [str(i+1) for i in range(N) if res[i] == 1]
l = len(ans)
if l > 0:
    print(l)
    print(' '.join(ans))
else:
    print(0)

Submission status: Accepted

Solution code:
import numpy as np
import copy

N = int(input())  
a = np.array(input().split(), dtype=np.int32)
M = np.arange(N) + 1
    
for i in np.arange(N // 2)[::-1]:
    A = a[i::i+1]
    if np.sum(A) % 2  == 0:
        a[i] = 0
    else:
        a[i] = 1
        
ans = np.where(a == 1)[0] + 1

print(np.size(ans))

if np.size(ans) > 0:
    print(*ans.astype(np.int32))

Submission status: Accepted

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

B = [0] * (N)
BB = []
cnt_b = 0
for i in range(N)[::-1]:
    sum_b = 0
    idx = 1
    while True:
        if (i+1) * idx > N:
            B[i] = (A[i] + sum_b)%2
            if B[i] == 1:
                cnt_b += 1
                BB.append(i+1)
            break
        else:
            sum_b += B[(i+1)*idx-1]
        idx += 1
print(cnt_b)
str_b = ' '.join(map(str, BB))
if str_b != '0':
    print(str_b)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

def main():
    # # 整数の入力
    # a = int(input())
    # # スペース区切りの整数の入力
    # b, c = map(int, input().split())
    # # 文字列の入力
    # s = input()
    # # 出力
    # print("{} {}".format(a+b+c, s))
    N = int(input())
    a_list = [int(i) for i in input().split()]
    b_list = [0] * N
    ret_b = []

    # a_listの後ろから順に検討していき，箱にボールをいれるかどうかが
    # 決定していく
    for i, a in enumerate(a_list[::-1]):
        index = N - 1 - i # N-1 --> 0
        ball_sum = get_sum(index, b_list)
        # print('ball_sum', ball_sum)
        if ball_sum % 2 != a:
            b_list[index] = 1
            ret_b.append(index + 1)
        # print(index)
        # print(b_list)
    print(len(ret_b))
    if len(ret_b)>0:
        print(' '.join(map(str, ret_b)))




def get_sum(index, b_list): # index: 0-(N-1)
    index_ = index + 1
    cur = index_
    ret_sum = 0
    while (cur<len(b_list)+1):
        ret_sum += b_list[cur-1]
        cur += index_
    return ret_sum


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    A = [-1] + A
    ans = 0
    B = [0] * (N+1)
    ans = []
    for i in range(N, 0, -1):
        s = 0
        for j in range(i, N+1, i):
            s += B[j]
        if s % 2 != A[i]:
            B[i] = 1
            ans.append(i)
    
    print(len(ans))
    if ans:
        print(' '.join(map(str, ans)))


def main():
    N = read_int()
    A = read_int_n()
    slv(N, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
l = [0 for i in range(N)]
ans = []
cnt = 0
for i in reversed(range(N)):
    j = 2
    memo = 0
    while (i+1)*j <= N:
        memo += l[(i+1)*j-1]
        j += 1
    memo = memo%2
    
    if memo != a[i]:
        l[i] = 1
        cnt += 1
        ans.append(str(i+1))
ans.sort()
print(cnt)
print(" ".join(ans))

Submission status: Accepted

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

MOD = 2  # type: int

def solve(N: int, a: "List[int]"):
    def isodd(ai: int):
        flag = False
        hoge = N // ai

        while True:
            if hoge == 1:
                break
            if ans[ai * hoge -1]:
                flag = not flag
            hoge = hoge - 1
        return flag

    sum = 0
    num = []
    ans = [0] * N

    for i in reversed(range(1, N+1)):
        odd = isodd(i)
        write = not (odd == a[i-1])

        if write:
            sum = sum + 1
            num.append(i)
            ans[i-1] = 1

    print(sum)
    if sum != 0:
        print(' '.join(map(str, num)))
    return

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
a = [int(x) for x in input().split()]
b = [0]*N
for i in range(N-1,-1,-1):
    if a[i] != sum([b[x] for x in range(i,N,i+1)]) % 2:
        b[i] = 1
print(b.count(1))
if b.count(1) != 0:
    print(" ".join([str(x+1) for x in range(N) if b[x]==1]))

Submission status: Accepted

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

def make_divisors(n):
  divisors = []
  for i in range(1, int(n ** 0.5) + 1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n // i)
  return divisors

a.reverse()
check = [0 for _ in range(N + 1)]
ball = []
for i in range(N):
  if check[N - i] % 2 != a[i]:
    ball.append(N - i)
    div = make_divisors(N - i)
    for d in div:
      check[d] += 1

print(len(ball))
for i in range(len(ball)):
  print(ball[i], end = "")
  if i != len(ball) - 1:
    print(" ", end = "")
  else:
    print()

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(bool, map(int, input().split())))
As.insert(0, False)
Ans = [False for _ in range(N + 1)]
Ans[N] = As[N]
for i in range(N - 1, 0, -1):
    p = i * 2
    s = False
    while p <= N:
        s ^= Ans[p]
        p += i
    Ans[i] = s ^ As[i]
M = sum(Ans)
print(M)
if M > 0:
    c = True
    for i in range(1, N + 1):
        if Ans[i]:
            if c:
                c = False
            else:
                print(" ", end="")
            print(i, end="")
    print("")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
#n = 3
#a = [1, 0, 0]
#n = 10
#a = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
b = [0] * n
for i in range(n // 2, n):
    b[i] = a[i]
#print(a)
#print(b)
for i in range(n // 2, 0, -1):
    s = sum(b[(i*2)-1:n:i])
    b[i - 1] = (s % 2) ^ a[i - 1]
    #print("i:{} s:{} b[{}]:{}".format(i, s, i - 1, b[i - 1]))
print(sum(b))
ans = ""
for i in range(n):
    if b[i] == 1:
        ans = ans + "{} ".format(i + 1)
print(ans.strip())

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0]*N
for i, a in enumerate(A[::-1]):
    if N - i > N // 2:
        B[-(i+1)] = 1 if a == 1 else 0
    else:
        x = N-i
        n = 2
        c = 0
        while N >= x*n:
            if B[x*n-1] == 1:
                c += 1
            n += 1
        if c % 2 == 1:
            B[-(i + 1)] = 0 if a == 1 else 1
        else:
            B[-(i + 1)] = 1 if a == 1 else 0

M = B.count(1)
if M:
    ans = []
    print(M)
    for i, v in enumerate(B):
        if v == 1:
            ans.append(i+1)
    print(*ans)
else:
    print(0)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
AS=[0]*N
ans=[]
div=N//2
div
j=1
for i in reversed(range(N)):
    if i+1 <= div:
        j=N//div
        div=N//(j+1)
    at=0
    for jt in range(j):
        at+=AS[(i+1)*(jt+1)-1]
    if at%2!=A[i]:
        ans.append(i+1)
        AS[i]=1

ans.reverse()
print(len(ans))
for i in ans:print(str(i)+' ',end="")

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import perm
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

########

N = i_inpl()
A = l_inpl()

ans = [0] * N
flag = True
for i in range(N)[::-1]:
    num = i+1
    cnt = N//num
    if cnt == 1:
        ans[i] = A[i]
    else:
        tmp = 0
        for j in range(1, cnt+1):
            tmp += ans[j*num-1]
        tmp %= 2
        if tmp == A[i]:
            ans[i] = 0
        elif tmp != A[i]:
            ans[i] = 1
        else:
            flag = False
            break
if flag:
    print(sum(ans))
    l = []
    for ind, i in enumerate(ans):
        if i != 0:
            l.append(str(ind+1))
    if sum(ans) != 0:
        print(" ".join(l))
else:
    print("-1")

Submission status: Accepted

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

b_s = [0 for _ in range(n)]
for i in range(n - 1, -1, -1):
  name = i + 1
  m_sum = a_s[i]
  for m_name in range(2 * name, n + 1, name):
    m = m_name - 1
    m_sum += b_s[m]
  b_s[i] = m_sum % 2

b_s_in = [str(i + 1) for i in range(n) if b_s[i] > 0]
print(len(b_s_in))
print(" ".join(b_s_in))

Submission status: Accepted

Solution code:
n = int(input())
li = list(map(int,input().split()))
li = [-1] + li

dp = [-1] * (n+1)
cnt = n
tmp = 0
s = -1
#print(li)

for i in range(1,n+1):
    for j in range(0,n+1,cnt):
        if j == 0:
            continue
        if s == -1:
            s = j
        if dp[-i] == -1:
            dp[-i] = li[j]
        tmp += dp[j]
        #print(i,j,tmp,li[j])
    
    if tmp%2 != li[s]:
        tmp -= dp[s]
        dp[s] = (li[s]+1)%2
        tmp += dp[s]
        if tmp%2 != li[s]:
            print(-1)
            exit()
    cnt -= 1
    tmp = 0
    s = -1

#print(dp)
print(dp.count(1))
ans = list([i for i,x in enumerate(dp) if x == 1])
print(*ans)

Submission status: Accepted

Solution code:
import math

N = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)
l = [0] * (N + 1)

flag = 0
s = sum(a)
if s == 0:
    print("0")
    exit()

for i in range(N, 0, -1):
    i_max = math.floor(N / i)

    if i_max == 1:
        l[i] = a[i]
    else:
        tmp = 0
        for j in range(i_max, 1, -1):
            tmp += l[i * j]


        if tmp % 2 == a[i]:
            l[i] = 0
        else:
            l[i] = 1

print(sum(l))
for i in range(1, N + 1):
    if l[i] == 1:
        print(i, " ")

Submission status: Accepted

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

for n in range(N // 2, 0, -1):
    if A[n-1] == sum(A[2*n-1:N:n]) % 2:
        A[n-1] = 0
    else:
        A[n-1] = 1

ans = sum(A)
print(ans)
if ans > 0:
    print(*[i+1 for i, a in enumerate(A) if a == 1], sep=" ")

Submission status: Accepted

Solution code:
from copy import deepcopy
n = int(input())
A = list(map(int,input().split()))
AA = deepcopy(A)
f = [0]*n
m = 0
b = []
for i in range(n-1,0,-1):
    if A[i]%2==0:
        continue
    b.append(i+1)
    m += 1
    for k in range(1,int((i+1)**0.5)+1):
        if (i+1)%k == 0:
            if(k-1!=(i+1)//k-1):
                A[k-1] -= 1
                A[(i+1)//k-1] -= 1
                f[k-1] += 1
                f[(i+1)//k-1] += 1
            else:
                A[k-1] -= 1
                f[k-1] += 1

if f[0]%2 !=AA[0]%2:
    b.append(1)
    m += 1
for i in range(1,n):
    if f[i]%2 != AA[i]:
        print(-1)
        exit()
print(m)
if m==0:
    exit()
print(*b)

Submission status: Accepted

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

#n ... 番目の箱　b[n-1]　のボールの数
blist = []
for j in range(n-1,-1,-1):
    k=j+1
    count= 0
    while k<=n:
        count = count + b[k-1]
        k = k+j+1
    if a[j] == 1:
        if (count)%2 == 0:
            b[j] = 1
            blist.append(j+1)
    else:
        if (count)%2 == 1:
            b[j] = 1
            blist.append(j+1)

sb = sum(b)
print(sb)
strb = " ".join(map(str,blist))
print(strb)

Submission status: Accepted

Solution code:
n = int(input())
a = tuple(map(int, input().split()))
b = [0] * n
ret = 0
ret2 = []
append = ret2.append
for i in range(n, 0, -1):
  count = 0
  for j in range(i+i, n+1, i):
    count += b[j-1]
  # print((i, count))
  if not (count % 2) == a[i-1]:
    b[i-1] = 1
    ret += 1
    append(i)

# print(b)
print(ret)
if ret == 0:
  exit()

# print(*reversed(ret2))

for i in range(n):
  if b[i] == 1:
    print('%d ' % (i+1), end="")

Submission status: Accepted

Solution code:
n = int(input())
lis = [0]
lis2 = list(map(int,input().split()))
lis_a = lis+lis2
if n %2 ==0:
    flag_a = [0] * (int(n/2)+1)
    for i in range(int(n/2),n):
        flag_a.append(lis_a[i+1])
else:
    flag_a = [0] * (int(n//2)+1)
    for i in range((n//2),n):
        flag_a.append(lis_a[i+1])
for i in range((n//2),0,-1):
    temp_sum = 0
    j = 2
    while (i*j <=n):
        temp_sum += flag_a[i*j]
        j += 1
    if temp_sum % 2 == 0:
        if lis_a[i] == 1:
            flag_a[i] = 1
        else:
            flag_a[i] = 0
    else:
        if lis_a[i] == 1:
            flag_a[i] = 0
        else:
            flag_a[i] = 1

print(flag_a.count(1))
anslis = []
for i in range(n+1):
    if flag_a[i] == 1:
        anslis.append(i)
strin = ""
for item in anslis:
    strin += str(item) + " "
if len(anslis):
    print(strin)

Submission status: Accepted

Solution code:
import copy

N = int(input())

a = [int(x) for x in input().split()]
b = copy.copy(a)

for i in range(N//2, 0, -1):
    num = 0
    for j in range(2*i, N+1, i):
        num += b[j-1]
    #     print(i, j, b[j-1])
    # print(i, num)
    if a[i-1] == divmod(num, 2)[1]:
        b[i-1] = 0
    else:
        b[i-1] = 1

# print(b)

ret = []
for i in range(N):
    if b[i] == 1:
        ret.append("{}".format(i+1))
print(len(ret))
print(" ".join(ret))

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    N = int(stdin.readline().rstrip())
    As = [int(x) for x in stdin.readline().rstrip().split()]
    result = [0 for _ in range(N)]
    for i, a in enumerate(As[::-1]):
        num = N - i
        idx = num - 1
        if N // num < 2:
            result[idx] = a
        else:
            sum_ = 0
            cnt = 2
            while True:
                if N < (num * cnt):
                    break
                sum_ += result[(num * cnt) - 1]
                cnt += 1
            if sum_ % 2 == 1:
                result[idx] = 1 if a == 0 else 0
            else:
                result[idx] = 0 if a == 0 else 1
    print(len([x for x in result if x == 1]))
    for i, x in enumerate(result):
        if x == 1:
            print(i + 1, end=' ')


if __name__ == "__main__":
    main()