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:
import numpy as np


def main():
	#N, D = [int(x) for x in input().split()]
	N = int(input()) + 1
	a = [0]
	a += [int(x) for x in input().split()]
	b = [0] * (len(a))

	counter = 0
	for i in range(N-1, 0, -1):
		num = 0
		for j in range(i, N, i):
			num += b[j]
		if not num % 2 == a[i]:
			b[i] += 1
			counter += 1
	if max(b) > 1:
		print(-1)
		return
	print(counter)
	l = [i for i, x in enumerate(b) if x == 1]
	for row in l:
		print(row, end=" ")
	print("")

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
def make_divisors(n):
    #divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            B[i]+=1
            if i != n // i:
                B[n//i]+=1

    # divisors.sort()
    #return divisors

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

B=[0]*300000
C=[]
count=0
for i in reversed(range(N)):
    if B[i+1]%2!=A[i]:
        make_divisors(i+1)
        count +=1
        C.append(i+1)
print(count)
#print(B)
if count!=0:
    for i in reversed(range(1,count)):
        print(str(C[i])+" ",end="")
    print(C[0], end="")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
a_list = list(map(int, input().split()))

M = 0
box_dict = {}
for i in reversed(range(N)):
    idx = i + 1
    multi_sum = 0
    if N // idx < 2:
        if a_list[i] == 0:
            box_dict[idx] = 0
        else:
            box_dict[idx] = 1
            M += 1
    else:
        for j in range(2, (N // idx) + 1):
            multi_sum += box_dict[idx * j]
        if a_list[i] - (multi_sum % 2) == 0:
            box_dict[idx] = 0
        else:
            box_dict[idx] = 1
            M += 1

print(M)
if M > 0:
    b_list = [key for key, value in box_dict.items() if value == 1]
    print(" ".join(map(str, b_list)))

Submission status: Accepted

Solution code:
import math

def myinput_int():
    return list(map(int, input().split()))
def myinput_int_special():
    text = '99 '+input() #インデックスが1から始まるように。99はダミー。
    return list(map(int, text.split()))

N, = myinput_int()
a = myinput_int_special()
answer=[-99]*(N+1)

for i in range(N,0,-1):
    goukei=0
    for j in range(2,math.floor(N/i)+1):
        goukei += answer[i*j]
    answer[i] = (goukei+a[i])%2

output=""
count=0
for i in range(1,N+1):
    if answer[i]==1:
        output+=' '+str(i)
        count+=1

output=output[1:] #先頭のスペースを除去。
print(count)
if output!="":
    print(output)

Submission status: Accepted

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

ls = [0]*n
for i in range(n-1,-1,-1):
    count = 0
    for j in range(i,n,i+1):
        count += ls[j]
    if (count + 1) % 2 == a[i]:
        ls[i] = 1
check = 0
for i in range(n):
    if ls[i] == 1:
        check += 1
    
print(check)
for i in range(n):
    if ls[i] == 1:
        print(i+1)

Submission status: Accepted

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

A = [None] + A
B = [0] * (N + 1)

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

B = [i for i, b in enumerate(B) if b == 1]
print(len(B))
for i in B:
    print(i)

Submission status: Accepted

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

b = [0] * N

for i in range(N//2, N) :
    b[i] = a[i]

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

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

print(cnt)
for i in range(len(ans)) :
    print(ans[i], end=" ")
if len(ans) > 0 :
    print()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
B = [0] * N
list_B = [0] * N

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

print(int(sum(B)))
list_B = ' '.join([str(a) for a in [i for i in list_B if i != 0]])
print(list_B)

Submission status: Accepted

Solution code:
N = int(input())
A=[-1]
A.extend([int(a) for a in input().split()])

ans = {}
ret = []

def get_xor(frm):
    global ans
    i = frm *2
    re = 0
    while i < len(A):
        re = re ^ ans[i]
        i += frm
    return re

for i in range(1,len(A)):
    ri = len(A) - i
    if 2 * ri < len(A):
        # recursive search
        ans[ri] = A[ri] ^ get_xor(ri)
        if ans[ri]==1:
            ret.append(str(ri))
        pass
    else:  # only one
        ans[ri] = A[ri]
        if ans[ri]==1:
            ret.append(str(ri))
print(len(ret))
s = " ".join(ret)
if s:
    print(s)

Submission status: Accepted

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

ans=[0]*n

i=n-1
j=1
f=0
while i!=-1:
    while True:
        try:
            b=i+(i+1)*j
            f+=ans[b]
            j+=1
        except:
            break
    f=f%2
    if (f-s[i])==0:
        ans[i]=0
    else:
        ans[i]=1
    j=1
    f=0
    i-=1
sad=[]
print(ans.count(1))
i=0
while i!=len(s):
    if ans[i]==1:
        sad.append(i+1)
    i+=1


print(' '.join(map(str, sad)))

Submission status: Accepted

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

for i in reversed(range(n)):
  if n/2 > i :
    tmp = 2
    sum_num = 0
    while (tmp*(i+1) - 1) < n:
      sum_num += 1 if b[tmp*(i+1)-1] == 1 else 0
      tmp += 1
      
    b[i] = 0 if sum_num %2 == a[i] else 1
  else:
    b[i] = a[i]
  
  if b[i] == 1:
    count += 1
    ans.append(str(i+1))
    
list.sort(ans)
print(count)
print(' '.join(ans))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
boxes = ["mada"] * n

for i in range(n, 0, -1):
    if boxes[i-1] == "mada":
        kokomade = sum((boxes[i-1::i])[1:]) % 2
        if kokomade == a[i-1]:
            boxes[i-1] = 0
        else:
            boxes[i-1] = 1

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

print(len(ans))
print(" ".join(ans))

Submission status: Accepted

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

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

for i in range(n, 0, -1):
    k = n // i

    an = a[i-1]

    for j in range(2,k+1):
        an = an ^ ans[j*i-1]

    ans[i-1] = an

print(sum(ans))
ans_l = [i+1 for i,x in enumerate(ans) if x == 1]
print(" ".join(map(str,ans_l)))

Submission status: Accepted

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

for i, a in enumerate(A[::-1]):
    ind = N - i
    if ind > N//2:
        ans[ind-1] = a
    else:
        cnt = 0
        for j in range(2, (N // ind) + 1):
            cnt += ans[j * ind - 1]
        if cnt % 2 == A[ind-1]:
            ans[ind-1] = 0
        else:
            ans[ind-1] = 1

print(sum(ans))
for i, a in enumerate(ans):
    if a == 1:
        print(i+1, end="")
        print(' ', end="")

Submission status: Accepted

Solution code:
from collections import deque

def main():
    n = int(input())
    A = list(map(int, input().split()))
    ans = 0
    B = [0] * n
    # ansList = []
    ansList = deque()

    def makeList(num):
        start = num + 1
        mul = n // start
        return [start * j - 1 for j in range(1, mul+1)]


    def makeRes(indices):
        flag = 0
        for elm in indices:
            if B[elm] == 1:
                flag = (flag + 1) % 2
        return flag


    for i in range(n-1, -1, -1):
        if i + 1 >  n / 2:
            if A[i] == 1:
                B[i] = 1
                ans += 1
                ansList.appendleft(i+1)
        else:
            indices = makeList(i)
            # print(indices)
            res = makeRes(indices)
            # print(res)
            if A[i] != res:
                B[i] = 1
                ans += 1
                ansList.appendleft(i+1)

    print(ans)

    if ans != 0:
        print(*(list(ansList)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=[0]*n
for j in range(n):
    i=n-j-1
    #print("元の数")
    #print(i+1)
    sum=a[i]
    for k in range(2,n+1):
        if((i+1)*k>n):
            break
        #print(i*k+k)
        sum=sum^ans[i*k+k-1]
    ans[i]=sum

#print(ans)

kazu=0
for i in range(n):
    if(ans[i]==1):
        kazu+=1
print(kazu)
for i in range(n):
    if(ans[i]==1):
        print(i+1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=[0]+[int(i) for i in input().split()]
b=[0]*(n+1)
only=int(n/2)
for i in range(only+1,n+1):
    b[i]=a[i]
if n%2==1:
    only+=1
for i in range(n-(only),0,-1):
    sum1=0
    for j in range(i,n+1,i):
        sum1+=b[j]
    if sum1%2==a[i]:
        b[i]=0
    else:
        b[i]=1
m=b.count(1)
print(m)
for i in range(1,n+1):
    if b[i]==1:
        print(i,end=" ")

Submission status: Accepted

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

ans_list=[0]*(n+1)
output=[]
for i in range(n,0,-1):
  #print("i",i)
  siji=a_list[i]
  num=n//i
  #print("num",num)
  tmp=0
  for j in range(1,num+1):
    #print("j",j,ans_list[i*j])
    tmp+=ans_list[i*j]
  #print("ans_list",ans_list)
  #print("siji",siji)
  #print(tmp)
  if tmp%2==siji:
    ans_list[i]=0
  else:
    ans_list[i]=1
    output.append(i)
    
print(sum(ans_list[1:]))
for i in range(len(output)):
    if i == len(output)-1:
      print(output[i])
    else:
      print(output[i],end=" ")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

import collections

def solve():
    N = int(input())
    a_list = list(map(int, input().split()))

    y_dict = collections.defaultdict(list)

    # 約数dictの自分の倍数のところに自分を入れる
    for i in range(1, N//2+2):
        cnt = 2
        while True:
            baisu = i * cnt
            y_dict[baisu].append(i)
            cnt += 1
            if baisu > N:
                break

    dprint(y_dict)
    bits = collections.defaultdict(int)
    ans = []
    # 逆順で見ていき、約数listに入っているもののbitを反転させる
    for i in range(N, 0, -1):

        a = a_list[i-1]
        dprint(a, bits[i])
        if a == bits[i]:
            continue
        for y in y_dict[i]:
            bits[y] = (bits[y] + 1) % 2
        ans.append(i)


    print(len(ans))
    print(' '.join([str(num) for num in reversed(ans)]))

solve()

Submission status: Accepted

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

for i in reversed(ama):
    if sum(a[n-1::n])%2==i:
        next
    else:
        a[n-1]=(a[n-1]+1)%2
    n=n-1


print(sum(a))
print(" ".join(list(map(str,list(map(lambda x: x+1, [i for i, x in enumerate(a) if x == 1]))))))


#for i in range(n):
#    print(max(num[:i]+num[i+1:]))

Submission status: Accepted

Solution code:
import sys
from collections import deque
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

B=[0]*N
kazu = 0
for i in range(N, 0, -1):
	num = N//i
	total = 0
	for n in range(1, num + 1):
		total += B[i*n - 1]
	total = total % 2
	if total != a[i - 1]:
		B[i - 1] = 1
		kazu += 1

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

print("\n")

Submission status: Accepted

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

def main():
  n = int(input())
  alist = list(map(int, input().split()))
  ans = [0 for _ in range(n+1)]
  anss = 0
  res = []
  for i in range(n, 1, -1):
    if ans[i]%2 != alist[i-1]:
      anss += 1
      res.append(i)
      j = 1
      while j*j <= i:
        if i % j == 0:
          if j*j == i:
            ans[j] += 1
          else:
            ans[j] += 1
            ans[i//j] += 1
        j += 1
    
  if ans[1] %2 != alist[0]:
    print(anss+1)
    res.append(1)
    res.reverse()
    print(*res)
  else:
    print(anss)
    if res:
      res.reverse()
      print(*res)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0]*(n+1)
for i in reversed(range(1,n+1)):
    tmp_num=i
    tmp=0
    while tmp_num<=n:
        tmp+=b[tmp_num]
        tmp_num+=i
    b[i]=(a[i-1]+tmp)%2
cnt=0
c=[]
for i in range(len(b)):
    if b[i]==1:
        cnt+=1
        c.append(str(i))
print(cnt)
if cnt!=0:
    print(" ".join(c))

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, 0, -1):
    if i > N // 2:
        C[i-1] = A[i-1]
    else:
        sum_b = 0
        for k in range(1, 10**6):
            if i * k > N:
                break
            else:
                sum_b += C[i * k - 1]
        if sum_b % 2 == A[i-1]:
            C[i-1] = 0
        else:
            C[i-1] = 1

print(sum(C))
B = []
for i in range(N):
    if C[i] == 1:
       B.append(i+1)
for i in range(len(B)):
    if i == len(B) - 1:
        print(B[i], end=" ")
    else:
        print(B[i], end=" ")

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))[::-1]
B=[0]*n
for i in range(n):
  k=n-i
  if A[i]!=(B[k-1::k].count(1))%2:
    B[k-1]=1
    
o=B.count(1)
print(o)
P=[[i+1 for i, x in enumerate(B) if x ==1]]
if o!=0:
  print(*P[0])

Submission status: Accepted

Solution code:
#

#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop
import math

def main():
    n = int(input())
    al = list(map(int, input().split()))

    ans = [0] * n

    half = math.ceil(n/2)
    for i in range(half, n):
        ans[i] = al[i]

    for i in range(half-1, -1, -1):
        num = i + 1
        val = 0
        for j in range(num * 2 - 1, n, num):
            # print(j)
            val += ans[j]

        val %= 2
        ans[i] = 0 if val == al[i] else 1

    c = ans.count(1)
    print(c)
    if c > 0:
        boxes = []
        for i in range(len(ans)):
            if ans[i] == 1:
                boxes.append(i + 1)
        print(' '.join(map(str, boxes)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import *
from math import log
from itertools import accumulate
from collections import deque
#maxv=[0]
import sys
sys.setrecursionlimit(100100)

import math
from math import ceil
from bisect import bisect_left


from copy import deepcopy
from itertools import permutations

from math import sqrt
from heapq import *
from math import factorial
from collections import defaultdict

#A,B=map(inr,input().split())
#a=list(map(int,input().split()))
from bisect import bisect_left as bl
from bisect import bisect_right as br
from math import log

from fractions import gcd
import math
from collections import deque

import sys
input=sys.stdin.readline
#s=input()
#l=list(map(int,input().split()))
N=int(input())
A=list(map(int,input().split()))
A=[0]+A
B=[0 for i in A]
def prime_factor(n):
    i = 2
    table = defaultdict(int)
    while i * i <= n:
        while n % i == 0:
            n //= i
            table[i]+=1
        i += 1
    if n > 1:
        table[n]+=1
    return table
K=[]
for n in range(N,0,-1):
    if A[n]-B[n]==0:
        continue
    K.append(n)
    table=prime_factor(n)
    #print(table)
    l=[1]
    if n==1:
        continue
    for i,j in table.items():
        l_=[]
        for k in l:
            l_.extend([k*i**m for m in range(1,j+1)])
        l.extend(l_)
    #print(l)
    for i in l:
        B[i]=1-B[i]
    #print(B)
#print(A)
#print(B)
if len(K):
    print(len(K))
    print(*K,sep=" ")
else:
    print(len(K))

Submission status: Accepted

Solution code:
def resolve():

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

    ans = [0] * n

    for i in range(n)[::-1]:

        bit = sum(ans[i:n:i+1]) % 2
        if bit != ai[i]:
            ans[i] = 1

    print(sum(ans))

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    s = list(map(int,input().split()))
    r = [0] * n
    for i in range(n,n//2,-1):
        if s[i-1] == 1:
            r[i-1] = 1
    for i in range(n//2,0,-1):
        p = n // i
        c = 0
        for j in range(1,p+1):
            if r[(j * i) - 1] == 1:
                c += 1
        if c % 2 != s[i-1]:
            r[i-1] = 1

    o = sum(r)
    print(o)
    if o > 0:
        u = []
        for i in range(len(r)):
            if r[i] == 1:
                u.append(str(i+1))
        print(" ".join(u))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i in range(N)[::-1]:
  if(not sum(B[::i+1])%2 == A[i]):
    B[i+1] = 1
  if(not sum(B[::i+1])%2 == A[i]):
    print(-1)
    quit()
  
print(sum(B))
for i, b in enumerate(B):
  if b == 1:
    print(i, end=" ")

Submission status: Accepted

Solution code:
#i+1の倍数の和
def sum_remainder_before_i(i, a):
    ans = 0
    j = 1
    while True:
        if (j+1)*(i+1)-1 > len(a)-1:
            return ans
        else:
            ans = ans + a[(j+1)*(i+1)-1]
            j = j + 1

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

i = N - 1
ans = [-1]*N
result = False

while True:
    sum = sum_remainder_before_i(i, ans)
    if sum % 2 == a[i]:
        ans[i] = 0
    else:
        ans[i] = 1
    if i == 0:
        break
    i = i - 1

m = 0
answers = []
for i, a in enumerate(ans):
    if a == 1:
        answers.append(i+1)
        m = m + 1

print(m)
if m > 0:
    print(" ".join(map(str,answers)))

Submission status: Accepted

Solution code:
import math

n = int(input())

ans = [0] * n

def baisuu(num, max):
    ret = []
    i = num
    while i <= max:
        ret.append(i)
        i = i + num
    return ret
    

# print("{}".format(baisuu(4,4)))

an = list(map(int, input().split()))

for i in range(n):
    sum = 0
    for mltp in baisuu(n-i, n):
        sum = sum+ans[mltp-1]
    if not sum % 2 == an[n-i-1]:
        ans[n-i-1] = 1
                     

ans = list(map(lambda x: x%2,ans))
print("{}".format(ans.count(1)))

for i in range(n):
    if ans[i] == 1:
        print("{}".format(i+1))

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
x = [-1]*N
b = []
for i in range(N,0,-1):
    m = N//i
    x[i-1] = int(sum(x[j] for j in range(i*2-1,i*m,i)) % 2 != a[i-1])
    if x[i-1] == 1:
        b.append(i)
print(len(b))
if len(b) > 0:
    print(" ".join(map(str, b)))

Submission status: Accepted

Solution code:
N = int(input())
List = list(map(int,input().split()))
found = True
A = []
B =[]
for i in range(N):
    a = N - i
    k = N // a
    c = 0
    for j in range(1,k):
        c += A[N - (j+1)*a]
    b = (List[a-1]-c)%2
    A.append(b)
    if b == 1:
       B.append(a) 
print(sum(A))
print(*B)

Submission status: Accepted

Solution code:
import sys
N=int(input())
A=list(map(int,input().split()))
c=1+N//2
ans=[-1 for _ in range(N+1)]
c_box=[]
total=0
b=[]
for i in range(c,N+1):
    ans[i]=A[i-1]
    if A[i-1]==1:
        c_box.append(i)
        total+=1
    
for i in range(c-1,0,-1):
    tmp=0
    for j in range(i*2,N+1,i):
        tmp+=ans[j]
    if tmp%2==0 and A[i-1]==0 or tmp%2==1 and A[i-1]==1:
        ans[i]=0
    elif tmp%2==1 and A[i-1]==0 or tmp%2==0 and A[i-1]==1:
        ans[i]=1
        c_box.append(i)
        total+=1
    else:
        print(-1)
        exit()
    
print(total)   
if total>0:
    print(" ".join(map(str,sorted(c_box))))

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

# N <= 2*10^5
# 1以上N以下の任意の整数iについて、iの倍数が書かれた箱に入っている
# ボールの個数の和を2で割った余りがaiである
N = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split()]
a = [None] + a

box = [0 for _ in range(N)]
box = [None] + box

for i in range(N, 0, -1):
    baisu_list = []
    for j in range(1, N+1):
        tmp = i * j
        if tmp > N:
            break
        else:
            baisu_list.append(tmp)

    in_list = []
    not_in_list = []

    for cur in baisu_list:
        if box[cur] == 1:
            in_list.append(cur)
        else:
            not_in_list.append(cur)

    if a[i] == len(in_list)%2:
        pass
    else:
        if not_in_list:
            box[not_in_list[0]] = 1
        else:
            print(-1)
            exit()


b = [i for i in range(1, N+1) if box[i] == 1]

print(len(b))
if b:
    print(*b, sep=" ")

Submission status: Accepted

Solution code:
import math

N = int(input())
a_list = [-1] + list(map(int, input().split()))

b_list = [None] * (N + 1)
for i in range(N, 0, -1):
	b = a_list[i]
	for j in range(i * 2, N + 1, i):
		b = b ^ b_list[j]
	b_list[i] = b

count = 0
b_list2 = []
for i in range(1, N + 1):
	if b_list[i] == 1:
		count += 1
		b_list2.append(str(i))

print(count)
print(" ".join(b_list2))

Submission status: Accepted

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

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

    return divisors

box = []
for i in range(n - 1, -1, -1):
    ind = make_divisors(i + 1)
    if num[i] % 2 != a[i]:
        for j in ind:
            num[j] += 1
        box.append(i + 1)
print(len(box))
print(*box)

Submission status: Accepted

Solution code:
import math


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)

    # divisors.sort()
    return divisors


N = int(input())
As = list(map(int, input().split(" ")))
As = [0] + As
kosu = [0] *(N+1)

anss = []
bs  = [0] *(N+1)
for i in range(N,N//2,-1):
    if As[i] == 0:
        bs[i] =0
    else:
        bs[i] = 1

for i in range(N// 2, 0, -1):
    temp = 0
    for k in range(1,N + 1):
        if i * k > N:
            break
        if bs[i * k] == 1:
            temp += 1
    if As[i] % 2  != temp %2:
        bs[i] = 1
print(bs.count(1))
for i,num in enumerate(bs):
    if num == 1:
        print(i)
# print(M)
# for i in ans:
#     print(i)

Submission status: Accepted

Solution code:


def solve():
    N = int(input())
    A = [int(i) for i in input().split()]
    ans = A.copy()
    for i in reversed(range(1, N // 2 + 1)):
        tag = i * 2
        tmp = 0
        while tag <= N:
            tmp += ans[tag - 1]
            tag += i
        ans[i - 1] = 1 if tmp % 2 != ans[i - 1] else 0

    print(sum(ans))
    s = ''
    for i, a in enumerate(ans, 1):
        if a == 1:
            s += str(i) + ' '
    if s != '':
        print(s.strip())


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N=int(input())
a = list(map(int,input().split()))
# N = 2*10**5
# a = [0 for i in range(N)]

fail = False
r = [0 for i in range(N)]
for i in range(N)[::-1]:
  tmpsum = 0
  for t in range(2,(N//(i+1))+1):
#     print(f"  {t*(i+1)}")
    tmpsum += r[(i+1)*t-1]
  diff = (a[i]-tmpsum)%2
#   print(diff)
  if diff == 1:
    r[i] = 1
  elif diff == 0:
    r[i] = 0
  else:
    fail = True
    break

if fail:
  print(-1)
else:
  print(sum(r))
#   print(" ".join(map(str,r)))

  result = []
  for i in range(N):
    if r[i]==1:
      result.append(i+1)
  if len(result) > 0:
    print(" ".join(map(str,result)))

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())

a = [int(i) for i in input().split()]
a = np.array(a)
b = np.zeros(n)
b_ind = np.arange(1, n + 1)
b[n // 2 + 1:] = a[n // 2 + 1:]

for i in range(n // 2 + 1, 0, -1):
    if np.sum(b[i - 1::i]) % 2 == a[i - 1]:
        b[i - 1] = 0
    else:
        b[i - 1] = 1

m = b[b == 1].shape[0]
print(m)
if m != 0:
    print(" ".join(map(str, b_ind[b == 1])))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = [0 for _ in range(N)]
half = int(N / 2) + 1
s = 0
hako = []
# if N % 2 == 0:
#     half = int(N / 2)

for i in reversed(range(N)):
    if i+1 >= half:
        if A[i] == 1:
            ans[i] = 1
            s += 1
            hako.append(i+1)
    else:
        cur = (i+1)*2
        tmp = 0
        while cur <= N:
            if ans[cur-1] == 1:
                tmp += 1
            cur += i+1
        if tmp % 2 != A[i]:
            ans[i] = 1
            s += 1
            hako.append(i+1)

print(s)
if len(hako) > 0:
    print(*hako)

Submission status: Accepted

Solution code:
N =int(input())
As = [int(x) for x in input().split()]
res = [0]*(N)
ks = range(N)

for i in range(N-1,N//2,-1):
    res[i] = As[i]
for i in range(N//2,0,-1):
    res[i] = (As[i]+sum(res[i::(i+1)]))%2
res[0] = (As[0]+sum(res[1:]))%2
ans =[]
for i,v in enumerate(res):
    if v==1:
        ans.append(i+1)
print(len(ans))
print(" ".join(map(str,ans)))

Submission status: Accepted

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

INPUT_L = [0] + A[:]
B = [0] * (N+1)

# 決まるものを入れてしまう
for i in range(N//2+1, N+1):
    B[i] = INPUT_L[i]
    
for i in reversed(range(1, N//2+1)):
    #print('__', i)
    #print(B[i::i])
    sum_b = sum(B[i::i])
    if sum_b % 2 == INPUT_L[i]:
        continue
    else:
        B[i] = 1
    
ans_sum = sum(B)

if ans_sum % 2 != INPUT_L[1]:
    print(-1)
else:
    #print(B)
    ans_list = []
    for i, b in reversed(list(enumerate(B))):
        if b != 0:
            ans_list.append(str(i))

    print(ans_sum)
    print(' '.join(ans_list))

Submission status: Accepted

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

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

def rec(i) :
    if i == N + 1 :
        return
    rec(i+1)
    s = 0
    for j in range(i, N + 1, i) :
        s ^= ret[j]
    ret[i] = s^a[i]
    
rec(1)
b = []
for i in range(1, N + 1) :
    if ret[i] :
        b.append(str(i))
print(len(b))
print(' '.join(b))

Submission status: Accepted

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

for i in range(n):
    x = n-i
    if(a[x-1] == 0):
        tmp = 0
        for j in range(int(n/x)):
            if(b[x*(j + 1)-1] == 1):
                tmp += 1
        if(tmp % 2 == 1):
            b[x-1] = 1
    else:
        tmp = 0
        for j in range(int(n/x)):
            if(b[x*(j + 1)-1] == 1):
                tmp += 1
        if(tmp % 2 == 0):
            b[x-1] = 1

ans = 0
ANS = []
for i in range(n):
    if(b[i] == 1):
        ans += 1
        ANS.append(i)
print(ans)
for i in range(len(ANS)):
    print(ANS[i]+1, end=' ')

Submission status: Accepted

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

# print(N, A)
B = [0]*N

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

for i in range(N // 2):
    index = N // 2 - i - 1
    num = 0
#     print(index)
    for j in range(1, N // (index + 1) + 1):
        v = j * (index + 1) - 1
        num += B[v]
        # print(v, B[v])
#     print(index, num)
    if num % 2 != A[index]:
        B[index] = 1
# print(B)

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

Submission status: Accepted

Solution code:
N = int(input())
a = [int(x) for x in input().split()]
isball = [0]*N
ball_list = []
oddeven = 0
for i in reversed(range(1, N)):
    ball_sum = 0
    for j in range(1, N // (i + 1)+1):
        ball_sum += isball[((j) * (i+1))-1]
    if ball_sum % 2 != a[i]:
        ball_list.append(i + 1)
        isball[i] = 1
        oddeven += 1

if oddeven % 2 != a[0]:
    ball_list.append(1)

print(len(ball_list))
print(*ball_list)

Submission status: Accepted

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

def func1(lst, value):
    return [i for i, x in enumerate(lst) if x == value]

for i in range(N,0,-1):
    #print("i:"+str(i))
    #print("sum(b[i::i])%2="+str(sum(b[i::i])%2))
    b[i] = a[i]^(sum(b[i::i])%2)
    #print(b[i])

print(sum(b[1:]))
idx = func1(b,1)
print(*idx)

Submission status: Accepted

Solution code:
import sys
import math

input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
ans = [0]*N
for i in range(N-1,-1,-1):
    if i > N//2 - 1:
        ans[i] = a[i]
    else:
        sm = 0
        for j in range(i+i+1, N, i+1):
            sm += ans[j]
        if sm % 2 == a[i]:
            ans[i] = 0
        else:
            ans[i] = 1

out = ''
for i in range(N):
    if ans[i] == 1:
        out += str(i+1) + ' '
print(ans.count(1))
print(out)