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(i) for i in input().split()]
ans = [0]*N

for i in reversed(range(1,N+1)):
  c = N//i
  if c==1:
    if a[i-1]==1:
      ans[i-1]=1
  else:
    d = 0
    for j in range(2,c+1):
      d += ans[i*j-1]
    ans[i-1]=(d+a[i-1])%2
#    print(i,c,j,d,a[i])
print(sum(ans))
if sum(ans)!=0:
  for i in range(len(ans)):
    if ans[i]==1:
      print(i+1, end=" ")

Submission status: Accepted

Solution code:
n = int(input())
dat = list(map(int, input().split()))
res = [0] * n
#print("dat: {0}".format(dat))
for i in range(n, 0, -1):
    # i-1で参照すること
    #print(i)
    t = 0
    for j in range(0, n // i):
        #print("add:{0}".format( str( ((j+1) * i) -1 )  ))
        t += res[ ((j+1) * i) -1]

    #print("i[{0}]:  t = {1}".format(i, t))

    if t % 2 == 1:
        if dat[i-1] == 1:
            res[i-1] = 0
        else:
            res[i-1] = 1
    else:
        if dat[i-1] == 1:
            res[i-1] = 1
        else:
            res[i-1] = 0

    #print(res[i-1])
    #print("res: {0}".format(res))

#print(res)

c = 0
for i in range(n):
    if res[i] == 1:
        c += 1

resl = []
resc = c
for i in range(n):
    if c == 0:
        break
    if res[i] == 1:
        c -= 1
        resl.append(str(i + 1))
    else:
        pass
        # resl.append("0")

print( resc )
if resc !=0:
    print(" ".join(resl))

Submission status: Accepted

Solution code:
import sys

import math

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

ball_arr = [0] * N

for i in range(math.floor(N/2), N):
    ball_arr[i] = a[i]
    
# print(ball_arr)

for i in reversed(range(math.floor(N/2))):
    # print(i)
    # print(i+1)
    # print(sum(ball_arr[i-1::i+1]))
    # print(sum(ball_arr[i-1::i+1]) != a[i])
    mul_arr = ball_arr[i::i+1]
    # print(mul_arr)
    if sum(mul_arr) % 2 != a[i]:
        # print((mull_arr.index(0)+1)*i)
        if 0 in mul_arr: 
            ball_arr[(mul_arr.index(0)+1)*i] = 1
        else:
            print(-1)
            sys.exit()
    # print(ball_arr)
    # print('---')
# print(ball_arr)

M = sum(ball_arr)
print(M)
for i, v in enumerate(ball_arr):
    if v == 1:
        print(i+1, end=' ')

Submission status: Accepted

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

n = int(input())
a = list(map(int, input().split()))
b = [0]*n
for i in range(n, 0, -1):
    temp = 0
    if n//i == 1:
        b[i-1] = a[i-1]
    else:
        for j in range(2, n+1):


            if i*j > n:
                break
            temp += b[i*j-1]
        if a[i-1] == 1:
            b[i-1] = 1 - temp%2
        else:
            b[i-1] = temp%2
print(sum(b))
for i in range(n):
    if b[i] == 1:
        print(i+1, "", end="")
print()

Submission status: Accepted

Solution code:
from sys import stderr
N = int(input())
A = [int(i) for i in input().split()]

B = [0] * N

for i in range(N // 2, N):
    B[i] = A[i]

for i in reversed(range(N // 2)):
    s = sum(B[i::i + 1])
    B[i] = (A[i] - s) % 2

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0]*n
m=n//2-1
if m>=0:
  for i in range(n-1,m,-1):
    b[i]=a[i]
for i in range(m,0,-1):
  x=n//(i+1)
  s=0
  for j in range(2,x+1):
    s+=b[(i+1)*j-1]
  if a[i]==0:
    b[i]=s%2
  else:
    b[i]=(s+1)%2
if a[0]==0:
  b[0]=sum(b)%2
else:
  b[0]=(sum(b)+1)%2
c=[]
for i in range(n):
  if b[i]==1:
    c.append(i+1)
print(len(c))
for i in c:
  print(i)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0]*N
n = N
for a in (reversed(A)):
    if n*2 > N:
        B[n-1] = a
        n -= 1
        continue
    total = 0
    for i in range(2,N+2):
        if n*i <= N:
            total += B[n*i-1]
        else:
            if a == total % 2:
                B[n-1] = 0
            else:
                B[n-1] = 1
            break
    n -= 1

M = sum(B)
print(M)
C = [str(n+1) for n, v in enumerate(B) if v == 1]
print(' '.join(C))

Submission status: Accepted

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

def solve(N: int, a: "List[int]"):
    dp = [0] * N
    for i in range(N, 0, -1):
        if i > N // 2:
            dp[i-1] = a[i-1]
        else:
            for j in range(2, N // i+1):
                dp[i-1] += dp[j * i - 1]
            dp[i-1] += a[i-1]
            dp[i-1] %= 2
    print(sum(dp))
    s = []
    for i in range(N):
        if dp[i] == 1:
            s.append('%d' % (i + 1))
    if len(s) > 0:
        print(' '.join(s))
    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_list = [int(i) for i in input().split()]
ans = ""
ans_list = [0]*N
for i in range(N, 0, -1):
  sum_ = 0
  for j in range(1, N//i+1):
    if j == 1:
      sum_ += ans_list[i*j-1]
    sum_ += ans_list[i*j-1]
    sum_ %= 2
  if sum_ != a_list[i-1]:
    ans_list[i-1] = 1

for i in range(N, 0, -1):
  sum_ = 0
  for j in range(1, N//i+1):
    sum_ += ans_list[i*j-1]
    sum_ %= 2
  if sum_ != a_list[i-1]:
    print(-1)
    exit()

for i, a in enumerate(ans_list):
  if a == 1:
    ans += str(i+1) + " "
print(sum(ans_list))
if ans:
  print(ans[:-1])

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))
b = [None for _ in range(N)]
for i in range(N):
    j = N-i
    if j > N//2:
        b[j-1] = a[j-1]
    else:
        s = 0
        for k in range(2*j-1, N, j):
            s = (s+b[k])%2
        b[j-1] = (a[j-1]-s) % 2
ans = []
for i in range(N):
    if b[i] == 1:
        ans.append(i+1)
if ans == []:
    print(0)
else:
    print(len(ans))
    print(" ".join(map(str, ans)))

Submission status: Accepted

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

ans = {}

for i in range(N)[::-1]:
    cnt = 0
    a = N // (i+1)
    b = [((j+1)*(i+1)) for j in range(a)]

    if len(b) > 1:
        for n in b[1:]:
            cnt += ans[n-1]
        tmp = cnt % 2
        if tmp == 0:
            ans[i] = li[i]
        else:
            ans[i] = (li[i] + 1)%2 
    else:
        ans[i] = li[i]
        
print(sum(ans.values()))
answer = [ str(i+1) for i in ans.keys()  if ans[i] == 1]
print(" ".join(answer))

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
    su = 0
    #print(i)
    #print((i,i**k+i,i))
    for j in range(i,i*k+i,i):
        su += ANS[j-1]
    if (su%2)!=A[i-1]:
        ANS[i-1] += 1

#print(ANS)

print(sum(ANS))
for i in range(len(ANS)):
    if ANS[i]==1:
        print(i+1)

Submission status: Accepted

Solution code:
N = int(input())

a = list(map(int, input().split()))
b = [0] * N
flag = True

for k in range(N):
    i = N - k
    count = 0
    for m in range(i, N + 1, i):
        count += b[m - 1]

    if count % 2 == a[i - 1]:
        pass
    elif (count + 1) % 2 == a[i - 1]:
        b[i - 1] = 1
    else:
        print(-1)
        flag = False
        break

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

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n = int(input())
    a = [int(s) for s in input().split()]
    b = [0] * n
    for i in range(n, 0, -1):
        b[i - 1] = a[i - 1]
        j = i + i
        while j <= n:
            b[i - 1] ^= b[j - 1]
            j += i
    m = b.count(1)
    print(m)
    if m:
        print(*(i + 1 for i, x in enumerate(b) if x))

Submission status: Accepted

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
data = [int(x) for x in stdin.readline().rstrip().split()]
data = [0] + data
ans = [0] * (N+1)
for i in range(N,0,-1):
    if data[i] == 1 and sum(ans[::i]) % 2 == 0: 
        ans[i] = 1
    elif data[i] == 0 and sum(ans[::i]) % 2 != 0:
        ans[i] = 1
print(sum(ans))
for ind,k in enumerate(ans):
  if k != 0:
    print(ind,end=" ")

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()))

a.insert(0, -1)

env = [0] * (n+1)
hako = [0] * (n+1)
ind = []

for _ in range(n):
    i = n - _
    if a[i] != env[i]:
        hako[i] = 1
        ind.append(str(i))
        yakusuu = make_divisors(i)
        for j in yakusuu:
            if env[j] == 0:
                env[j] = 1
            else:
                env[j] = 0

goukei = sum(hako)
print(goukei)
if ind != []:
    mojiretu = ' '.join(ind)
    print(mojiretu)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = []
temp = [0]*n
for i in range(n):
    x = n-i
    y = 0
    for j in range(n):
        if x*(j+2) <= n:
            if temp[x*(j+2)-1] == 1:
                y += 1
        else:
            break
    if not y%2 == a[x-1]:
        ans.append(x)
        temp[x-1] += 1
s = len(ans)
print(s)
if s > 0:
    print(" ".join([str(i) for i in ans]))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

ans_flag = False
B =[0]*N
B[N//2:] = A[N//2:]
for idx in list(reversed(range(N//2))):
  sum_bai = sum(B[idx::idx+1]) % 2
  
  if A[idx] == 0:
    if sum_bai == 0:
      B[idx] = 0
    else:
      B[idx] = 1
  else:
    if sum_bai == 0:
      B[idx] = 1
    else:
      B[idx] = 0
      
M = sum(B)
B_ans = [idx+1 for idx in range(N) if B[idx] == 1]
print(M)
print(' '.join(list(map(str, B_ans))))

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
b=[0]*N
c=[]
cnt=0
for i in range(1,N+1)[::-1]:
  if sum(b[i-1::i])%2 != a[i-1]:
    b[i-1]=1
    c.append(i)
    cnt+=1
print(cnt)
if len(c)>0:
  print(*c,sep='\n')

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [0]*n
for i in range(n-1,int(n/2)-1,-1):
  b[i] = a[i]
for i in range(int(n/2)-1,-1,-1):
  c = [(i+1)*x for x in range(1,int(n/(i+1))+1)]
  s = 0
  for j in c:
    s += b[j-1]
  s = s%2
  if s != a[i]:
    b[i] = 1
if sum(b) == 0:
  print(0)
else:
  print(sum(b))
  k = 0
  for i in range(n):
    if b[i] == 1:
      if k == 0:
        print(i+1,end = "")
        k = 1
      else:
        print("",i+1,end="")

Submission status: Accepted

Solution code:
N=int(input())
A=[0]+[int(_) for _ in input().split()]
ans=[0]*(N+1)
result=[]
for i in range(N,0,-1):
    bai=N//i
    if A[i]!=sum(ans[i*b] for b in range(2,bai+1))%2:
        ans[i]=1
        result+=[i]
print(len(result))
print(*result)

Submission status: Accepted

Solution code:
# ABC134d
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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


for i in range(n, 0, -1):
    j = 1
    su = 0
    while (i * j <= n):
        su += ans[i * j]
        j += 1
    # print(str(i)+"は"+str(su))
    if (su % 2 == a[i]):
        # print("なので"+str(i)+"を0")
        ans[i] = 0
    else:
        # print("なので"+str(i)+"を1")
        ans[i] = 1

# print(ans)

s = ""
c = 0
for i in range(n+1):
    if (ans[i] == 1):
        c += 1
        s += str(i)+" "
print(c)
if(c != 0):
    print(s)

Submission status: Accepted

Solution code:
import sys
n=int(input())
L=[0 for i in range(n+1)]
a=list(map(int,input().split()))
if n==1 and a[0]==1:
  print(1)
  print(1)
  sys.exit()
for i in range((n//2)+1,n+1):
  L[i]=a[i-1]
  if L[i]==1:
    for j in range(1,int(i**0.5)+1):
      if i%j==0:
        L[j]+=1
        if j*j!=i and j!=1:
          L[i//j]+=1
for i in range(n//2,0,-1):
  L[i]=(a[i-1]+L[i])%2
  if i!=1 and L[i]==1:
    for j in range(1,int(i**0.5)+1):
      if i%j==0:
        L[j]+=1
        if j*j!=i and j!=1:
          L[i//j]+=1
ct=0
for i in range(1,len(L)):
  if L[i]==1:ct+=1
print(ct)
ans=[]
for i in range(1,len(L)):
  if L[i]==1:ans.append(str(i))
print(' '.join(ans))

Submission status: Accepted

Solution code:
def solve():
    n = int(input())
    A = [0] + list(map(int, input().split()))
    for i in range(n // 2, 0, -1):
        t = len([1 for k in range(i, n + 1, i) if A[k] == 1]) & 1
        if A[i] != t:
            A[i] = 1 - A[i]
    print(sum(A))
    print(*list(i for i in range(1, n + 1) if A[i]))
solve()

Submission status: Accepted

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

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

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

print(M)
print(' '.join(c))

Submission status: Accepted

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

ball = [0]*(n+1)
for j in range(n//2+1, n+1):
    ball[j] = a[j-1]
for i in range(n//2, 0, -1):
    summ = 0
    for k in range(2, n+1):
        if i*k > n:
            break
        else:
            summ += ball[i*k]
    if a[i-1] == (summ%2):
        ball[i] = 0
    else:
        ball[i] = 1

print(sum(ball))
if sum(ball) > 0:
    ans = []
    for l in range(1, n+1):
        if ball[l] == 1:
            ans.append(l)
    print(' '.join(map(str, ans)))

Submission status: Accepted

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

b = [0 for _ in range(n)]

for i, e in enumerate(a[::-1]):
    _sum = sum(b[n-1 - i: n: n-i])
    if _sum % 2 == e:
        pass
    else:
        b[n-1 - i] = 1

ball_cnt = sum(b)
print(ball_cnt)
if ball_cnt > 0:
    boxes = [i + 1 for i, e in enumerate(b) if e == 1]
    print(" ".join(map(str, boxes)))

Submission status: Accepted

Solution code:
import sys
from math import floor

n= int(sys.stdin.readline())
a= [ int(x) for x in sys.stdin.readline().split() ]
ans= [-1]*n
c = floor(n/2) + 1
for i in range(c,n+1):
    j= i-1
    ans[j]= a[j]
#
for i in range(c-2,-1,-1):
    j= i+1
    s= a[i]
    for k in range(2*j,n+1,j): s+= ans[k-1]
    ans[i]= s%2
#
m= sum(ans)
print( m )
if m>0:
    for i in range(n):
        if ans[i]: print( i+1,end=" " )

Submission status: Accepted

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


main()

Submission status: Accepted

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

dp = [0] * N
for i in reversed(range(N)):
    cnt = sum(dp[i::i + 1])
    if cnt % 2 == a[i]:
        dp[i] = 0
    else:
        dp[i] = 1
            
if True:
    b_bin = [i + 1 for i in range(N) if dp[i] > 0]
    print(len(b_bin))
    print(*b_bin)
else:
    print(-1)

Submission status: Accepted

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

cnt = 0
for i in range(1, n + 1)[::-1]:
    s = sum([l[(j + 2) * i - 1] for j in range(n // i - 1)])
    l[i - 1] = (s + a[i - 1]) % 2
    cnt += l[i - 1]

print(cnt)
ju = 0
for i, k in enumerate(l):
    if k != 0:
        if (ju == 1):
            print(" ", end="")
        if (ju == 0):
            ju = 1
        print(i + 1, end="")
if ju == 1:
    print()

Submission status: Accepted

Solution code:
import math
import sys


def nontrivial_divisors(x):
	for i in range(1, math.floor(math.sqrt(x)) + 1):
		d, m = divmod(x, i)
		if m == 0:
			if i != x:
				yield i
			if d != x:
				yield d


def solve(n, qs):
	ps = [0] # sent.
	ps.extend(qs)
	balls = [0] * (n + 1)
	vals = [0] * (n + 1)
	divs = [set() for _ in range(n + 1)]
	for i in range(1, n // 2 + 1):
		for j in range(2, n // i + 1):
			divs[i * j].add(i)
	# print(divs, file=sys.stderr)
	first = n // 2 + 1
	last = n
	while True:
		for i in range(first, last + 1):
			if vals[i] % 2 != ps[i]:
				balls[i] += 1
				vals[i] += 1
				for j in divs[i]:
					vals[j] += 1
		if first == 1:
			break
		last = first - 1
		first = last // 2 + 1
	for i in range(1, n + 1):
		if vals[i] % 2 != ps[i]:
			return None
	else:
		bs = [b for b in range(1, n + 1) if balls[b]]
		m = len(bs)
		return m, bs
	

def main():
	n = int(input())
	qs = [int(q) for q in input().split()]
	res = solve(n, qs)
	if res is None:
		print(-1)
	else:
		m, bs = res
		print(m)
		print(*bs)


if __name__ == "__main__":
	main()

Submission status: Accepted

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

for i in range(N, 0, -1):
  tmp = 0
  for j in range(N // i - 1):
    tmp += B[i * (j + 2) - 1]

  mod = tmp % 2
  if A[i - 1] == 0:
    if mod == 0:
      pass
    else:
      B[i - 1] = 1
      M.append(str(i))
  else:
    if mod == 0:
      B[i - 1] = 1
      M.append(str(i))
    else:
      pass

print(len(M))
if len(M) > 0:
  print(' '.join(M))

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))
ans = [0]*N
num_list = [list(map(lambda x: x-1,list(range(i+1,N+1,i+1)))) for i in range(N)]
for i in range(N)[::-1]:
  #print("num_list : {}".format(num_list[i]))
  before_num = sum([ans[i] for i in num_list[i]])
  #print("before_num%2 : {}".format(before_num%2))
  #print("a[i] : {}".format(a[i]))
  ans[i] = (before_num%2 + a[i])%2
  #print("ans[i] : {}".format(ans[i]))

if not (1 in ans):
  print(0)
else:
  print(ans.count(1))
  for i in range(N):
    if ans[i] == 1:
      print(i+1,end=" ")

Submission status: Accepted

Solution code:
import numpy

N = int(input())

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

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

ans = []

# print(a)

l = N//2

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

ind = l
for _ in range(l):
    # print("ind" , str(ind))
    # print("b")
    # print(b)
    ai = a[ind - 1]
    iter = N // ind - 1
    s = 0
    for j in range(1, iter+1):
        s += b[ind + j * ind - 1]
    # print("s = " + str(s))
    if (s % 2) == ai:
        b[ind - 1] = 0
    else:
        b[ind - 1] = 1
        ans.append(ind)

    if ind == 1:
        break
    else:
        ind -= 1
# print("b")
# print(b)
m = sum(b)
# print("m")
print(m)

if m != 0:
    for c in ans:
        print(c, end =" ")

Submission status: Accepted

Solution code:
import math

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

bline = line[:]
sep = math.ceil(n/2)
bline[:sep] = [0]*sep
# print([0]*sep)


for i in reversed(range(sep)):
    bline[i]=(sum(bline[i::i+1])+line[i])%2

blist=[]

for i in range(len(bline)):
    if bline[i]==1:
        blist.append(i+1)

# print(line)
# print(bline)
# print(blist)
print(len(blist))
print(' '.join(map(str,blist)))

Submission status: Accepted

Solution code:
N=int(input())
lst = [int(s) for s in input().split()]
ans=[0]*N
result=[]
def now(num):
  res=0
  k=1
  while(k*num<=N):
    res=res+ans[k*num-1]
    k=k+1
  return res%2
for i in range(N):
  n=N-i
  x=lst[n-1]
  y=now(n)
  if(x!=y):
    ans[n-1]=1
    result.append(n)
result.sort()
print(len(result))
if (len(result)!=0):
  print(' '.join(map(str, result)))

Submission status: Accepted

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

for i in reversed(range(n)):
    t = i+1
    if t*2 > n:
        b[i] = a[i]
    else:
        #print(i, b[i], i*2+1, a[i*2+1])
        b[i] = a[i*2+1]
        j = i + (t*2)
        #print(j,b[i])
        #print(b)
        while j < n:
            b[i] += b[j]
            #print(j, b[j], b[i])
            j += t*2
        b[i] = b[i] % 2
        #print(a[i], b[i])
        if b[i] == a[i]:
            b[i] = 0
        else:
            b[i] = 1

#print(b)
ans = []
for i in range(len(b)):
    if b[i] == 1:
        ans.append(str(i+1))
print(len(ans))
if len(ans) > 0:
    print(" ".join(ans))

Submission status: Accepted

Solution code:
N = int(input())
a = [0]
for x in input().split():
    a.append(int(x))
b = [0]*(N+1)
for i in range(1, N+1)[::-1]:
    if i > N//2:
        b[i] = a[i]
    else:
        b[i] = (a[i] + sum([b[j] for j in range(i, N+1, i)])) % 2

print(sum(b))
print(" ".join(map(str, [i for i in range(1, N+1) if b[i] == 1])))

Submission status: Accepted

Solution code:
import sys,math,copy
input = sys.stdin.readline

N=int(input().strip())
An=[int(x) for x in input().strip().split()]
Bn=[-1 for _ in range(N)]
Sum=0
for i in range(N-1,-1,-1):
    temp=0
    index=(i+1)*2
    while index <= N:
        temp=temp^Bn[index-1]
        index+=(i+1)

    ball= An[i] ^ temp
    Sum+=ball
    Bn[i]= ball

print(Sum)
if Sum!=0:
    ans=[str(x+1) for x in range(N) if Bn[x]==1]
    print(' '.join(ans))

Submission status: Accepted

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

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

for i in range(1, N + 1):
    for j in range(i, N + 1, i):
        baisuu[j].append(i)


ans = []
lst = [0 for _ in range(N + 1)]
for i in reversed(range(1, N + 1)):

    lst[i] = (lst[i] + A[i]) % 2
    if lst[i] == 1:
        ans.append(i)

    for j in baisuu[i]:
        lst[j] = (lst[j] + lst[i]) % 2

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

Submission status: Accepted

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

for i in range(mid, n):
    b[i] = a[i]

for i in range(mid-1, -1, -1):
    s = 0
    for j in range(i,n,i+1):
        s += b[j]
    if s%2 != a[i]:
        b[i] += 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()))
b=[0]*N
n=0
ans=[]
for i in reversed(range(N)):
    t=0
    for j in range(2*(i+1)-1,N,i+1):
        if b[j]==1:
            t^=1
    b[i]=a[i]^t
    if b[i]==1:
        n+=1
        ans.append(str(i+1))
print(n)
print(' '.join(ans))

Submission status: Accepted

Solution code:
n = int(input())

a = []
aa = input().split() 

for i in range(n):
    a.append(int(aa[i]))

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

memo = int(n/2)+2
for i in range(n-1,-1,-1):
    if i >= memo:
        ans[i] = a[i]
    else:
        memo2 = 0
        s = i+1
        t = 2
        while (s*t-1)<=(n-1):
            if ans[s*t-1] == 1:
                memo2 += 1
            t += 1
        if a[i] != memo2%2:
                ans[i] = 1

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

print(v)

for i in range(n):
    if ans[i] == 1:
        print(i+1,end="")
        print(" ",end ="")

Submission status: Accepted

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

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

print(sum(b))
if sum(b)!=0:
    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()))
ans=[0]*n
for i in range(n-1,-1,-1):
  if sum(ans[i::i+1])%2!=a[i]:
    ans[i]=1
ans=[i+1 for i in range(n) if ans[i]==1]
print(len(ans))
ans=list(map(str,ans))
ans=" ".join(ans)
print(ans)

Submission status: Accepted

Solution code:
a=int(input())
b=list(map(int,input().split()))
c=[0 for i in range(a)]
e=[]
i=a-1
while i>=0:
  d=(b[i]+sum(c[i::i+1]))%2
  if d==1:
    c[i]=1
    e.append(i+1)
  i-=1
print(len(e))
for i in range(len(e)):
  print(str(e[i]),end="")
  if i!=len(e)-1:
    print(" ",end="")

Submission status: Accepted

Solution code:
# coding: utf-8
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
a = np.insert(a,0,0)
#print(a)
box = np.zeros(n+1,dtype="int32")
#print(box)

for i in range((n//2)+1,n+1):
    if a[i] == 1:
        box[i] = 1
        
for i in reversed(range(1,(n//2)+1)):
    # odd
    if a[i]==1:
        if np.sum(box[i::i])%2==0:
            box[i] = 1
        else:
            box[i] = 0
    # even
    else:
        if np.sum(box[i::i])%2==1:
            box[i] = 1
        else:
            box[i] = 0
m = np.sum(box)
ans_index = np.where(box==1)[0]
#print(ans_index)
ans_index = map(str, ans_index)
print(m)
if m!=0:
    ans = " ".join(ans_index)
    print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from scipy.misc import comb
sys.setrecursionlimit(1000000)
 
n = int(input())

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

a.insert(0,0)

list_n = n + 1

box = [0] * (n+1)

one = []

for i in range(list_n-1):
    cnt = n - i
    tmp = 0
    for j in range(list_n):
        #print(cnt)
        if cnt * (j+1) <= n:
            tmp = ( tmp + box[cnt*(j+1)] ) % 2
        elif tmp == a[cnt]:
            box[cnt] = 0
            break
        else:
            box[cnt] = 1
            one.append(cnt)
            break
        
if len(one) == 0:
    print(0)
else:
    print(len(one))
    print(*one)

Submission status: Accepted

Solution code:
import math

N = int(input())
a = list(map(int, input().split(' ')))
a.insert(0, -1)
#print(a)

mid = math.floor(N / 2)
#print(mid)

M = 0
b = [0 for i in range(N)]
b.insert(0, -1)
for i in reversed(range(1, N + 1)):
    if i > mid:
        if a[i] == 0:
            b[i] = 0
        else:
            M += 1
            b[i] = 1
    else:
        num = 0
        for j in range(1, N // i + 1):
            num += b[j * i]
        if num % 2 == 0:
            if a[i] == 0:
                b[i] = 0
            else:
                M += 1
                b[i] = 1
        else:
            if a[i] == 0:
                M += 1
                b[i] = 1
            else:
                b[i] = 0

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

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int,input().split()))
half = n//2

ans = [0]*n
for i in range(half,n):
    if l[i] == 1:
        ans[i] = 1
for i in range(0,half):
    p = half-1-i
    s = 0
    qmax = n //(p+1)
    for j in range(1,qmax+1):
        s += ans[j*(p+1)-1]
    if s%2 != l[p]:
        ans[p] = 1
print(sum(ans))
for i in range(n):
    if ans[i] == 1:
        print(i+1,end=" ")

Submission status: Accepted

Solution code:
N = int(input())
a = [int(_) for _ in input().split()] 
b = [-1] * N

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

print(sum(b))

#print(b)
res = []
for i in range(N):
    if b[i] == 1:
        res.append(str(i+1))
print(" ".join(res))

Submission status: Accepted

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


import numpy as np


def solv(m, a):
    boxs = np.zeros(m, dtype=np.int)

    for i in range(m, 0, -1):
        # idx = np.arange(i+i-1, m, i)
        s = np.count_nonzero(boxs[i+i-1:m:i])
        boxs[i-1] = (s + a[i-1]) % 2

    return boxs


if __name__ == '__main__':

    m = int(input())
    a = np.array(list(map(int, input().split())), dtype=np.int)

    ans = solv(m, a)

    print(sum(ans))
    for i in range(m):
        if ans[i]:
            print(i+1)

Submission status: Accepted

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

if N == 1:
    if A[0] == 1:
        print(1)
        print(1)
        exit()

ans = [0 for _ in range(N // 2 + 1)] + A[N // 2:]

for i in range(N // 2, 1, -1):
    count = 0
    n = i
    j = 2
    while n * j <= N:
        count += ans[n * j]
        j += 1
    ans[i] = (count + A[i - 1]) % 2

sans = sum(ans)

ans[1] = (sans + A[0]) % 2

sans += ans[1]

print(sans)
p = ''
for i in range(1, N + 1):
    if ans[i] == 1:
        p += str(i) + ' '

print(p)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = [1 for i in range(N)]
for i,a in enumerate(A):
    i = N-i-1
    if i != 0:
        partsum = 0
        if i <= N//2-1:
            for j in range(N//(i+1)):
                k = j+1
                k *= (i+1)

                partsum += ans[k-1]

            if partsum % 2 != A[i]:
                ans[i] = 0
            
        else:
            if A[i] == 0:
                ans[i] = 0
    else:
        if sum(ans)%2 == A[i]:
            bans = []
            for bi, b in enumerate(ans):
                if b == 1:
                    bans.append(bi+1)
            print(len(bans))
            if len(bans) != 0:
                print(*bans)
        else:
            ans[i] = 0
            bans = []
            for bi, b in enumerate(ans):
                if b == 1:
                    bans.append(bi+1)
            print(len(bans))
            if len(bans) != 0:
                print(*bans)