Problem:


Score : 400 points

Problem Statement

There are N empty boxes arranged in a row from left to right.
The integer i is written on the i-th box from the left (1 \leq i \leq N).

For each of these boxes, Snuke can choose either to put a ball in it or to put nothing in it.

We say a set of choices to put a ball or not in the boxes is good when the following condition is satisfied:

For every integer i between 1 and N (inclusive), the total number of balls contained in the boxes with multiples of i written on them is congruent to a_i modulo 2.

Does there exist a good set of choices? If the answer is yes, find one good set of choices.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

a_i is 0 or 1.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

If a good set of choices does not exist, print -1.

If a good set of choices exists, print one such set of choices in the following format:

M
b_1 b_2 ... b_M

where M denotes the number of boxes that will contain a ball, and b_1,\ b_2,\ ...,\ b_M are the integers written on these boxes, in any order.

Sample Input 1

3
1 0 0

Sample Output 1

1
1

Consider putting a ball only in the box with 1 written on it.

There are three boxes with multiples of 1 written on them: the boxes with 1, 2, and 3. The total number of balls contained in these boxes is 1.

There is only one box with a multiple of 2 written on it: the box with 2. The total number of balls contained in these boxes is 0.

There is only one box with a multiple of 3 written on it: the box with 3. The total number of balls contained in these boxes is 0.

Thus, the condition is satisfied, so this set of choices is good.

Sample Input 2

5
0 0 0 0 0

Sample Output 2

0

Putting nothing in the boxes can be a good set of choices.



Sample input:
3
1 0 0


Sample output:
1
1

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

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

balls = np.array([0]*(n+1))

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

#print(balls)

ans = np.where(balls==1)[0].tolist()
if sum(balls):
    print(sum(balls))
    print(*ans)
else:
    print(0)

Submission status: Accepted

Solution code:
import numpy as np

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

balls = np.array([0]*(n+1))

for i in range(1,n+1):
    s = sum(balls[n+1-i::n+1-i])
    if (s%2 and not A[-i]) or (A[-i] and not s%2):
        balls[-i] += 1

#print(balls)

ans = np.where(balls==1)[0].tolist()
if sum(balls):
    print(sum(balls))
    print(*ans)
else:
    print(0)

Submission status: Accepted

Solution code:
import math

N = int(input())
a = list(map(int,input().split()))
b = []
x = math.ceil(N/2)
check = 0

for i in reversed(range(N-x)):
    flag = a[i]
    mul = i + 1
    for j in range(mul + mul -1,N,mul):
        check += a[j]
    if (check % 2 == 0 and flag == 0) or (check % 2 == 1 and flag == 1):
        a[i] = 0
    else:
        a[i] = 1
    check = 0

ans = a.count(1)
print(ans)
if ans == 0:
    exit()

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

print(*b)

Submission status: Accepted

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

al = [0] + al # 1-index
multi_cnts = [0]*(N+1)
ans = []
for n in range(N,0,-1):
    if multi_cnts[n] != al[n]:
        ans.append(n)
        for i in range(1, int(n**0.5)+1):
            if n%i == 0:
                multi_cnts[i]+=1
                multi_cnts[i]%=2
                if i*i != n:
                    multi_cnts[n//i]+=1
                    multi_cnts[n//i]%=2


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

Submission status: Accepted

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

a.insert(0,0)

for i in range(N,0,-1):
    count = 0
    check = 2*i
    while check <= N:
        count = (count+decided[check])%2
        check += i
    if a[i] == 1 and count == 1:
        continue
    elif a[i] == 0 and count ==0:
        continue
    else:
        decided[i] = 1

print(sum(decided))
answer = [i for i in range(N+1) if decided[i]==1]

print(" ".join(list(str(i) for i in answer)))

Submission status: Accepted

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

for i in range(N):
    Res[N-i] = A[N-i] ^ (sum(Res[::N-i]) % 2)

print(sum(Res))
ResN = []
for i,r in enumerate(Res):
    if i==0:
        continue
    if r == 1:
        ResN.append(str(i))

if ResN:
    print(' '.join(ResN)) # ここの空白を忘れてはならない

Submission status: Accepted

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

cnt = [0]*200010

b = []

for i in reversed(range(n)):

	num = i + 1
	if cnt[num]%2 != a[num-1]:
		b.append(num)
		j = 1
		while j*j <= (num):
			if num%j==0 :
				cnt[j] += 1
				if num//j != j:
					cnt[num//j]+=1
			j = j +1


print(len(b))
b.sort()

for i in b:
	print(str(i)+' ',end='')

print()

Submission status: Accepted

Solution code:
from collections import deque
n =int(input())
a = [0]+list(map(int, input().split()))
d = deque()
cnt=0
for i in range(n,0,-1):    
  for j in range(i,n+1,i):
    if a[j]==0:
      continue
    cnt+=1
  b = cnt%2
  a[i] = b
  if b == 1:
    d.appendleft(i)
  cnt = 0
print(len(d))
print(' '.join(map(str,d)))

Submission status: Accepted

Solution code:
from collections import deque
n =int(input())
a = [0]+list(map(int, input().split()))
d = deque()
cnt=0
for i in range(n,0,-1):    
  for j in range(i,n+1,i):
    if a[j]==0:
      continue
    cnt+=1
  b = cnt%2
  a[i] = b
  if b == 1:
    d.appendleft(i)
  cnt = 0
print(len(d))
print(' '.join(map(str,d)))

Submission status: Accepted

Solution code:
n = int(input())
a = [-1]
a.extend(list(map(int, input().split())))
cnt = 0
ansID = []
ans = [-1]*(n+1)

for i in reversed(range(1, len(a))):
  tmp = a[i]
  j = i*2
  while j < len(ans):
    tmp += ans[j]
    j += i
  ans[i] = tmp%2
  cnt += tmp%2
  if tmp%2 == 1:
    ansID.append(i)
  
print(cnt)
for ans in ansID:
  print(ans, end=" ")

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    input = stdin.readline
    n = int(input())
    a = [0] + list(map(int, input().split()))
    for i in range(n, 0, -1):
        a[i] = sum(a[i::i]) % 2
    print(sum(a))
    for i in range(1, n + 1):
        if a[i] == 1:
            print(i)
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:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

n=int(input())
a=list(map(int,input().split()))
cnt=[0]*n
ans=[]
d={}
for i in range(n,0,-1):
  flag=False
  for j in make_divisors(i):
    if a[i-1]==1 and cnt[i-1]%2==0:
      cnt[j-1]+=1
      flag=True
    elif a[i-1]==0 and cnt[i-1]%2==1:
      cnt[j-1]+=1
      flag=True
  if flag:
    ans.append(i)
print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
import sys

N = int(input())
A = [0] + list(map(int, sys.stdin.readline().rsplit()))

res = []
M = 0
tmp = [0] * (N + 1)
for i in reversed(range(1, N + 1)):
    cnt = 0
    for j in range(i, N + 1, i):
        cnt += tmp[j]
    if cnt % 2 != A[i]:
        tmp[i] = 1
        M += 1
        res.append(i)

print(M)
if M != 0:
    print(*res[::-1])

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
A = np.fromstring(input(), dtype=np.int32, sep=' ')
T = np.zeros(n, dtype=np.int32)

ans = []
for i in range(n-1, -1, -1):
  x = A[i]^np.logical_xor.reduce(T[i:n:i+1])
  if x:
    T[i] = 1
    ans.append(i+1)

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

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())

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

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

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())

x = [0] * (N + 1)
ans = []
for i in reversed(range(1, N + 1)):
    tmp = 0
    for j in range(i, N + 1, i):
        tmp += x[j]

    if tmp % 2 != A[i - 1]:
        x[i] += 1
        ans.append(i)

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

Submission status: Accepted

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

tmp = [0]*(N)
tmp_N = N

for i in range(N-1,-1,-1):
    tmp_c = 0
    for j in range(i,N,i+1):
        tmp_c += tmp[j]
    if tmp_c%2 == a[i]:
        tmp[i] = 0
    else:
        tmp[i] += 1

ans_c = 0
ans_b = []
for i in range(N):
    if tmp[i] != 0:
        ans_c += 1
        ans_b.append(i+1)
        
print(ans_c)
print(*ans_b)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    N = Scanner.int()
    A = Scanner.map_int()
    A = [0] + A
    B = [0 for _ in range(N + 1)]
    for i in reversed(range(1, N + 1)):
        j = i
        t = 0
        while j < N + 1:
            t += B[j]
            j += i
        if A[i] != t % 2:
            B[i] = 1
    ans = sum(B)
    print(ans)
    if ans > 0:
        print(*[i for i, b in enumerate(B) if b == 1], sep=' ')


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = [0] * n
ret = []
for i in range(n):
  j = n - i - 1
  count = A[j]
  num = j + 1
  while True:
    num += (j + 1)
    if num > n:
      break
    count += B[num - 1]
  if count % 2:
    B[j] = 1
    ret.append(j + 1)
print(len(ret))
print(*ret)

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    A = list(map(int, input().split()))
    M = 0
    ret_M = []
    memo_N = [0]*N # memo: 倍数を足したときに2で割った余り
    for i in range(N)[::-1]:
        i_ = i+1
        q = N//i_
        s = sum(memo_N[i_*(d+1)-1] for d in range(1,q))
        memo_N[i] = (s%2)^A[i]
        if memo_N[i]:
            M += 1
            ret_M.append(i_)
                
    print(M)
    if M: print(' '.join(map(str, ret_M[::-1])))
      
solve()

Submission status: Accepted

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

if sum(b) == 0:
  print(0)
else:
  print(sum(b))
  for i in range(n):
    if b[i] == 1:
      print(str(i + 1), end=" ")

Submission status: Accepted

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

for i in range(N, 0, -1):
    to = 0
    #print(i)

    for j in range(i-1, N ,i):
        to += b[j]

    if to%2 != a[i-1]:
        b[i-1] = 1
    #print(b)
if sum(b)==0:
    print(0)

else:
    print(sum(b))
    ans = str()
    for i in range(N):
        if b[i]:
            ans += str(i+1)+" "
    print(ans)

Submission status: Accepted

Solution code:
import sys
#import time
from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
#import heapq
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n = ri()
a = rl()

ans=[0]*n

for i in range(n,0, -1):
    sum_=0
    iter_=2
    while i*iter_<=n:
        sum_+=ans[i*iter_-1]
        iter_+=1

    if sum_%2!=a[i-1]:
        ans[i-1]=1

print(sum(ans))
if sum(ans)!=0:
    for i, num in enumerate(ans):
        if num==1:
            print(i+1)

Submission status: Accepted

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

def ii():
    return int(input())

def main():
    N = ii()
    a = [0]+list(mi())
    b = [0]*(N+1)
    for i in range(N, 0, -1):
        if i > N//2:
            b[i] = a[i]
        else:
            b[i] = (a[i]+sum(b[i*2::i]))%2
    print(sum(b))
    print(' '.join([str(i) for i in range(N+1) if b[i]]))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

boxes=[0]*(n+1)
m=0
b=[]
for i in reversed(range(1,n+1)):
    if sum(boxes[i::i])%2 != a[i]:
        boxes[i]=1
        m+=1
        b.append(i)
print(m)
print(*b)

Submission status: Accepted

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

b = [0]*n 
s = [0]*(n+1)

for i in reversed(range(1,n+1)):
	for k in range(1,math.floor(n/i)+1):
		j = int(k*i)
		s[i] += b[j-1]
	if s[i]%2 != a[i-1]:
		b[i-1] += 1

L = [i+1 for i in range(n) if b[i] == 1]
print(len(L))
print(*L)

Submission status: Accepted

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

b = [0]*n 
c = 0
s = [0]*(n+1)

for i in reversed(range(1,n+1)):
	for k in range(1,math.floor(n/i)+1):
		j = int(k*i)
		s[i] += b[j-1]
	if s[i]%2 != a[i-1]:
		b[i-1] += 1
		c += 1
print(c)
L = [i+1 for i in range(n) if b[i] == 1]
print(*L)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
n = int(input())
a = list(map(int, input().split()))

def func(n, a):
    x = [[] for i in range(n)]
    for i in range(n):
        d = make_divisors(i + 1)
        for j in d[:-1]:
            x[j - 1].append(i + 1)
    # print("x =", x)

    ans = [0 for i in range(n)]
    for i in reversed(range(n)):
        total = 0
        for j in x[i]:
            total += ans[j - 1]
        if total % 2 != a[i]:
            ans[i] = 1
    # print("ans =", ans)

    m = ans.count(1)
    print(m)
    # print("ans =", ans)
    for i in range(n):
        if ans[i] == 1:
            print(i + 1)
    # return ans

func(n, a)
# for n in range(1, 10):
#     for i in range(1 << n):
#         bit = bin(i)[2:].zfill(n)
#         a = [int(i) for i in bit]
#         ans = func(n, a)
#         for i in range(n):
#             total = ans[i]
#             for j in range(n):
#                 if i == j or (j + 1) % (i + 1) != 0:
#                     continue
#                 total += ans[j]
#             if total % 2 != a[i]:
#                 print("error")

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
chk = [0] * N 
ans = []
cnt = 0

for i in reversed(range(1,N+1)):
    if i > N // 2:
        if A[i-1] == 1:
            ans.append(i)
            chk[i-1] = 1
            cnt += 1
    else:
        j = 2 * i
        ret = 0
        while j <= N:
            ret += chk[j-1] 
            j += i
        if A[i-1] != ret%2:
            ans.append(i)
            chk[i-1] = 1
            cnt += 1
            
print(cnt)
print(*ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
mod = 10**9+7

N = i()
a = l()
table = [0]*N
ans = []
for i in range(N-1,-1,-1):
    bit = 0
    for j in range(i,N,i+1):
        bit = bit^table[j]
    bit = bit^a[i]
    if bit == 1:
        ans.append(i+1)
    table[i] = bit
print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    B = [False] * (N + 1)

    for i, a in reversed(list(enumerate(A, 1))):
        tmp = 0
        for j in range(2 * i, N + 1, i):
            tmp += B[j]
        B[i] = tmp % 2 != a

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    B = [False] * (N + 1)

    for i, a in reversed(list(enumerate(A, 1))):
        tmp = 0
        for j in range(2 * i, N + 1, i):
            tmp ^= B[j]
        B[i] = a ^ tmp

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    lower.extend(reversed(upper))
    return lower


def main():
    N, *A = map(int, read().split())

    B = [False] * (N + 1)
    C = [0] * (N + 1)

    for i in range(N, 0, -1):
        if A[i-1] == C[i]:
            continue
        B[i] = True
        divs = divisors(i)
        for d in divs:
            C[d] ^= 1

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    lower.extend(reversed(upper))
    return lower


def main():
    N, *A = map(int, read().split())

    B = [False] * (N + 1)
    C = [0] * (N + 1)

    for i, a in reversed(list(enumerate(A, 1))):
        if a == C[i]:
            continue
        B[i] = True
        divs = divisors(i)
        for d in divs:
            C[d] ^= 1

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    lower.extend(reversed(upper))
    return lower


def main():
    N, *A = map(int, read().split())

    B = [False] * (N + 1)
    C = [0] * (N + 1)

    for i, a in reversed(list(enumerate(A, 1))):
        if a == C[i] % 2:
            continue
        B[i] = True
        divs = divisors(i)
        for d in divs:
            C[d] += 1

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

S = sum(ans)
print(S)
if S:
    print(*[i+1 for i in range(N) if ans[i]])

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = [0] + a
ans = [0] * (n+1)
for i in range(n, 0, -1):
    now = 2 * i
    tmp = 0
    while now <= n:
        tmp += ans[now]
        now += i
    ans[i] = (a[i]-tmp)%2
print(sum(ans))
for i in range(n+1):
    if ans[i] == 1:
        print(i)

Submission status: Accepted

Solution code:
N=int(input())
binary=[int(s) for s in input().split()]

boxes=[0 for _ in range(N)]
ans=set()

for i in range(N-1,-1,-1):
  if sum(boxes[i::i+1])%2!=binary[i]:
    boxes[i]=1
    ans.add(i+1)
print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
N=int(input())
binaly=[int(s) for s in input().split()]

boxes=[0 for _ in range(N)]
ans=set()

for i in range(N-1,-1,-1):
  if sum(boxes[i::i+1])%2!=binaly[i]:
    boxes[i]=1
    ans.add(i+1)
print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = [0] + list(map(int, input().split()))
    B = [0] * (n + 1)
    res = []

    for i in reversed(range(1, n + 1)):
        if B[i] % 2 != A[i]:
            res.append(i)
            for j in range(1, int(pow(i, 0.5)) + 1):
                if i % j == 0:
                    B[j] += 1
                    if j != i // j:
                        B[i // j] += 1

    print(len(res))
    if len(res) != 0:
        print(*res[::-1])


def resolve2():
    n = int(input())
    A = [0] + list(map(int, input().split()))
    B = [0] * (n + 1)

    for i in reversed(range(1, n + 1)):
        cnt = 0
        for j in range(i, n + 1, i):
            cnt += B[j]
        if cnt % 2 != A[i]:
            B[i] += 1

    print(sum(B))
    if sum(B) != 0:
        print(*[i for i, ball in enumerate(B) if ball])


if __name__ == '__main__':
    resolve2()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = [0] + list(map(int, input().split()))
    B = [0] * (n + 1)
    res = []

    for i in reversed(range(1, n + 1)):
        if B[i] % 2 != A[i]:
            res.append(i)
            for j in range(1, int(pow(i, 0.5)) + 1):
                if i % j == 0:
                    B[j] += 1
                    if j != i // j:
                        B[i // j] += 1

    print(len(res))
    if len(res) != 0:
        print(*res[::-1])


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
kosuu = int(input())
dp = list(map(int,input().split()))
ans = []
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return set((lower_divisors + upper_divisors[::-1])[:-1])
for i in range(kosuu):
	hako = kosuu - i
	if dp[hako-1] == 1:
		for j in make_divisors(hako):
			dp[j-1] ^= 1
		ans.append(str(hako))
print(len(ans))
print(' '.join(ans))

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
ans = [0]*N
anss = []
ball = 0
for i in range(N, 0, -1):
    count = N//i
    total = 0
    for j in range(1, count+1):
        total += ans[i*j-1]
    if total%2 == a[i-1]:
        ans[i-1] = 0
    else:
        ans[i-1] = 1
        anss.append(i)
        ball += 1
if ball == 0:
    print(0)
else:
    print(ball)
    anss.reverse()
    print(" ".join(map(str, anss)))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [0] * n
ans = []
for i in range(n-1, -1, -1):
    if i == n-1:
        b[i] = a[i]
    else:
        sm = sum(b[i::i+1])
        b[i] = abs(a[i] - (sm % 2))
    if b[i] == 1:
        ans.append(i+1)
print(len(ans))
print(' '.join(map(str,ans)))

Submission status: Accepted

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

Submission status: Accepted

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

b =[0]*(n+1)

ans = 0

for i in range(n):
  j = n-i
  sum = 0
  m = 1
  while j*m <= n:
    sum += b[j*m]
    m += 1
  if sum % 2 != a[j-1]:
    b[j] = 1 
    ans += 1
    


if not 1 in b:
  print(0)
else:
  print(ans)
  for i in range(n+1):
    if b[i] == 1:
      print(i, end =' ')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def divisor(n):
    i = 1
    d = []
    while i * i <= n:
        if n % i == 0:
            d.append(i)
            if i * i != n:
                d.append(n // i)
        i += 1
    return d


def solve(N, A):
    use = [1 for i in range(N+1)]
    for i in range(N, 0, -1):
        multiple = sum([use[i] for i in range(i+i, N+1, i)])
        if A[i-1] == (1 + multiple) % 2:
            use[i] = 1
        else:
            use[i] = 0
    ans = [i for i in range(1, N+1) if use[i]]
    print(len(ans))
    if len(ans) > 0:
        print(*ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))
    B = [0] * n
    ans = []
    for i, a in enumerate(A[::-1]):
        i = n - i
        b = sum(B[i - 1::i])
        if b % 2 != a:
            ans.append(str(i))
            B[i - 1] = 1
    print(len(ans))
    print(' '.join(ans))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [0]*n
for i in range(n):
    b1=b[n-1-i::n-1-i+1]
    su=sum(b1)
    if (a[n-1-i]==0 and su%2==0) or (a[n-1-i]==1 and su%2==1):
        b[n-1-i]=0
    else:
        b[n-1-i]=1
ans =[]
print(sum(b))
for i in range(n):
    if b[i]==1:
        ans.append(str(i+1))
print(' '.join(ans))