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:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
  
def solve():
  n = int(input())
  a = list(int(i) for i in input().split())
  ans = [0]*n
  for i in range(n-1,-1,-1):
    if a[i] == 0:
      continue
    else:
      ans[i] = 1
      tmp = i+1
      div = make_divisors(tmp)
      ##print(div)
      for j in div:
        a[j-1] = 1^a[j-1]
        
  print(sum(ans))
  for i in range(len(ans)):
    if ans[i] == 1:
      print(i+1,end = " ")
solve()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [ 0 for _ in range(N+1) ]
ans = []
for i in range(1, N+1)[::-1]:
  c = 0
  for j in range(i, N+1, i):
    if B[j]:
      c += 1
  if c % 2 == A[i-1]:
    B[i] = 0
  else:
    B[i] = 1
    ans.append(i)
ans.sort()
print(len(ans))
print(" ".join([ str(x) for x in ans]))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
ball = [0 for i in range(n)]
count = 0 #ボールが入ってる箱の数
index = [] #ボールが入ってる番号

for i in range(n-1, -1, -1):
    balls = 0
    j = i
    while j +(i+1) < n:
        j += i + 1
        balls += ball[j]
    
    if a[i] != balls%2:
        ball[i] = 1
        count += 1
        index.append(i+1)
        
ans = ""
for i in range(len(index)):
    if i < len(index)-1:
        ans += str(index[i]) + " "
    else:
        ans += str(index[i])
print(count)
print(ans)

Submission status: Accepted

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

N = int(input())
L = [int(v) for v in input().split()]

s = {}
for i in reversed(range(N)):
    c = i + 1

    p = 0
    for v in range(c, N + 1, c):
        if s.get(v) == 1:
            p += 1

    if p % 2 != L[i]:
        s[c] = 1

t = list(s.keys())

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

Submission status: Accepted

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

M=0
for i in range(N,0,-1):
	sum = 0
	for j in range(i*2,N+1,i):
		sum += Bi[j-1]
	if sum % 2 == Ai[i-1]:
		Bi[i-1] = 0
	else:
		Bi[i-1] = 1
		M += 1

print(M)
for i in range(N):
	if Bi[i] == 1:
		print(i+1)

Submission status: Accepted

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

ans = [0]*n

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

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

Submission status: Accepted

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

for i in reversed(range(1,n//2+1)):
    b[i] = abs((sum([b[i*j] for j in range(2,n//i+1)])%2) - a[i])

m = len([b[i] for i in range(n+1) if b[i] == 1])
bb = list(map(str,[i for i in range(n+1) if b[i] == 1]))
print(m)
print(" ".join(bb))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import numpy as np

N = int(input())

A = list(map(int,input().split()))
B = A
ct = 0

for i in range(N):
    j = N-i-1
    if(j+1>N/2):
        B[j] = A[j]
        
        if(B[j]==1):
            ct = ct + 1
    else:
        sum = 0
        for k in range(j+1,N+1,j+1):
            if(k%(j+1)==0 and k!=j+1):
                
                sum = sum + B[k-1]
        if(sum%2==0):
            B[j] = A[j]
            if(B[j]==1):
                ct = ct + 1
        else:
            B[j] = 1 - A[j]
            
            if(B[j]==1):
                ct = ct + 1
        

print(ct)
C = []

for i in range(N):
    if(B[i]==1):
        C.append(i+1)
print(*C)

Submission status: Accepted

Solution code:
n=int(input())
info=list(map(int,input().split()))
info.insert(0,0)
box=[0]*(n+1)
ball=0
num=[] #ボールを入れた番号を記憶
for i in range(n,0,-1):
    j=i
    total=0
    while j<=n:
        total+=box[j]
        j+=i
    if total%2!=info[i]: #箱にボール入れる
        box[i]=1
        ball+=1
        num.append(i)

print(ball)
if ball!=0:
    l=len(num)
    for i in range(l):
        print(num[i],end=" ")

Submission status: Accepted

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

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

for i in range(N)[::-1]:
    s = N // (i+1)
    a = a_list[i]
    if s > 1:
        m_a = sum([b[(i+1)*k-1] for k in range(2, s+1)]) % 2
        a = a ^ m_a
    b[i] = a
print(sum(b))

res = ""
for i in range(len(b)):
    if b[i] > 0:
        res += str(i+1) + " "
if len(res) > 0:
    print(res)

Submission status: Accepted

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

num = len(a)
b = [0] * num

for i in reversed(range(1, num+1)):
    index = list(range(i, num+1, i))
    # print(index)
    count = 0
    for s in index:
        count += b[s-1]
    # print(count)

    if a[i-1] != count % 2:
        b[i-1] = 1

if max(b) == 0:
    print(0)
else:
    s = []
    for i, x in enumerate(b):
        if x == 1:
            s.append(i+1)
    print(len(s))
    print(" ".join(map(str, s)))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
ans = set()
 
for i in range(N-1,-1,-1):
    a = A[i]
    for j in range(i+1,N+1,i+1):
        if j in ans:
            a += 1
    if a%2:
        ans.add(i+1)
 
print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.readline
inf = 10 ** 18
P = 10 ** 9 + 7

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

x = [ai % 2 for ai in a]
for i_inv in range(N):
    i = (N - 1) - i_inv
    j = 2
    xi = x[i]
    # print("#", i, a[i])
    while (i + 1) * j - 1 < N:
        # print("##", (i + 1) * j - 1, x[(i + 1) * j - 1])
        xi ^= x[(i + 1) * j - 1]
        j += 1
    x[i] = xi

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

if sum(x) > 0:
    print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
from operator import xor

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


def multiples(n, m):
    # m以下のnの倍数を返す
    lst = list()
    num = n
    while True:
        if num <= m:
            lst.append(num)
            num += n
        else:
            break
    return lst


ans = [0] * (N + 1)
for i in reversed(range(1, N + 1)):
    s = 0
    for m in multiples(i, N):
        s += ans[m]
    s %= 2
    ans[i] = xor(s, A[i - 1])

s = sum(ans)
print(s)
if s != 0:
    print(' '.join([str(i) for i in range(1, N + 1) if ans[i] > 0]))

Submission status: Accepted

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

ans = set()

for i in range(N-1,-1,-1):
    a = A[i]
    for j in range(i+1,N+1,i+1):
        if j in ans:
            a += 1
    if a%2:
        ans.add(i+1)

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n = int(input())
a_array = [int(x) for x in input().split()]
ans_array = [0 for x in range(n)]
for index in reversed(range(1, n + 1)):
    if index > n // 2:
        ans_array[index - 1] = a_array[index - 1]
    elif index - 1 != 0:
        tmp = sum([ans_array[x] for x in range(index * 2 - 1, n, index) if ans_array[x] != 0]) % 2
        if tmp == a_array[index - 1]:
            pass
        else:
            ans_array[index - 1] = 1

    else:
        tmp = sum([x for x in ans_array[1:] if x != 0]) % 2
        if tmp == a_array[index - 1]:
            pass
        else:
            # tmpが0だったら1、1だったら0になるように
            ans_array[index - 1] = 1
print(sum([x for x in ans_array if x != 0]))
for index, ans in enumerate(ans_array, 1):
    if ans != 0:
        print(index)

Submission status: Accepted

Solution code:
n = int(input())

a = [0] + [int(i) for i in input().split()]
b = [0 for i in range(n+1)] 
ans = []

for i in range(n, 0, -1):
    s = 0
    for j in range(i*2, n+1, i):
        s ^= b[j]
    if s != a[i]:
        b[i] = 1
        ans.append(i)
print(len(ans))
print(' '.join(map(str, ans)))

Submission status: Accepted

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

c = [0] * (n+1)

for i in range(n, 0, -1):
    c[i] = a[i]
    tmp = i * 2
    while tmp <= n:
        c[i] -= c[tmp]
        tmp += i
    c[i] = c[i] % 2

print(sum(c))
for i in range(1, n+1):
    if c[i] == 1:
        print(i)

Submission status: Accepted

Solution code:
N = int(input())
L = [0] + list(map(int,input().split()))
N = len(L)
ans = [0 for i in range(N + 2)]
for i in reversed(range(1,N)):
    cnt = 0
    c = i
    while True:
        c += i
        if c > N:
            break
        cnt += ans[c]
    if cnt % 2 == 0 and L[i] == 0:
        ans[i] = 0
    elif cnt % 2 == 0 and L[i] == 1:
        ans[i] = 1
    elif cnt % 2 == 1 and L[i] == 0:
        ans[i] = 1
    else:
        ans[i] = 0 
c = 0
for i in range(len(ans)):
    if ans[i] == 1:
        c = i
ans = ans[1:c+1]

cnt = 0
for x in ans:
    if x == 1:
        cnt += 1
print(cnt)
for i in range(len(ans)):
    if ans[i] == 1:
        print(i+1,end = ' ')

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split()]

ans = []
for k in reversed(range(1, N + 1)):
    if a[k - 1] == 1:
        ans.append(k)
        tmp = 1
        while tmp * tmp <= k:
            if k % tmp == 0:
                a[tmp - 1] ^= 1
                if tmp != k // tmp:
                    a[k // tmp - 1] ^= 1
            tmp += 1

x = len(ans)
print(x)
if x >= 0:
    print(*ans)

Submission status: Accepted

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

    b = [0] * (N + 1) 

    for i in range(N,0,-1):
        sum = 0
        for j in range(2*i, N+1, i):
            sum += b[j]
        if sum % 2 != a[i] % 2:
            b[i] = 1
    
    ans = []
    for i in range(1,N+1):
        if b[i] == 1:
            ans.append(i)
    
    print(len(ans))
    print(*ans)

main()

Submission status: Accepted

Solution code:
N = int(input())
num_line = [0] + list(map(int, input().split()))
for i in range(N//2, 0, -1):
    num_line[i] = sum(num_line[i::i]) % 2
    #if sum(num_line[i::i]) % 2 != num_line[i]:
        #num_line[i] = 1
ans = [i for i, j in enumerate(num_line) if j == 1]
print(len(ans))
#print(" ".join(map(str, list(i for i in range(1, N+1) if num_line[i] == 1))))
print(*ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys, math, bisect, random, itertools
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    print(n*n*3)
    return

#B
def B():
    n, d = LI()
    print((n-1)//(2*d+1)+1)
    return

#C
def C():
    n = II()
    a = IR(n)
    b = a[::1]
    b.sort()
    for i in range(n):
        if a[i] == b[-1]:
            print(b[-2])
        else:
            print(b[-1])
    return

#D
def D():
    n = II()
    a = [0] + LI()
    for i in range(n // 2, 0, -1):
        x = sum(a[i::i])
        if x % 2 != a[i]:
            a[i] ^= 1
    ans = []
    x = 0
    for i in range(1, n + 1):
        if a[i]:
            ans.append(str(i))
            x += 1
    print(x)
    if x == 0:
        return
    print(" ".join(ans))
    return

#E
def E():
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

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

for num, val in list(enumerate(b))[::-1]:
    if not sum(bb[::num+1]) % 2 == val:
        bb[num+1] = 1
        ans.append(str(num+1))
print(len(ans))
if len(ans):
    print(' '.join(ans))

Submission status: Accepted

Solution code:
N = int(input())
num_line = [0] + list(map(int, input().split()))
for i in range(N//2, 0, -1):
    num_line[i] = sum(num_line[i::i]) % 2
    #if sum(num_line[i::i]) % 2 != num_line[i]:
        #num_line[i] = 1
print(num_line.count(1))
print(" ".join(map(str, list(i for i in range(1, N+1) if num_line[i] == 1))))

Submission status: Accepted

Solution code:
N = int(input())
inputs = [int(i) for i in input().split()]

ans = [0 for _ in range(N)]
for i in range(N-1, -1, -1):
    if sum(ans[i::i+1]) % 2 != inputs[i]:
        ans[i] = 1

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

Submission status: Accepted

Solution code:
n,a,d,l=int(input()),list(map(int,input().split())),set(),0;b=[0]*n
for i in range(n-1,-1,-1):
  c=0
  for j in range(2*i+1,n,i+1):c=(c+b[j])%2
  if a[i]!=c:b[i]+=1;d.add(i+1);l+=1
print(l)
print(*[d.pop()for _ in range(l)])

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0 for i in range(n)]
c=0
d=[]
for i in range(n-1,-1,-1):
  j=2
  c=b[i]
  while((i+1)*j<=n):
    c=c^b[(i+1)*j-1]
    j+=1
  if (c!=a[i]):
    b[i]=1
  c=0
  j=2
print('{0}'.format(sum(b)))
for i in range(n):
  if(b[i]==1):
    d.append(i+1)
e=list(map(str,d))
f=' '.join(e)
print('{0}'.format(f))

Submission status: Accepted

Solution code:
from collections import defaultdict

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

d = defaultdict(int)

#約数を求める
def makeDivisor(n):
    for i in range(1, int(n ** 0.5)+1):
        if n % i == 0:
            d[i] += 1
            if i != n // i:
                d[n//i] += 1
    return

b = [0] * N
cnt = 0
for i in range(N, 0, -1):
    if d[i] % 2 == 1 and a[i-1] == 0:
        b[i-1] = 1
        cnt += 1
        makeDivisor(i)
    elif d[i] % 2 == 0 and a[i-1] == 1:
        b[i-1] = 1
        cnt += 1
        makeDivisor(i)

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

Submission status: Accepted

Solution code:
#D 後ろから考えると一意に定まる、つまり答えは常に存在し、ただ一通りしかない。
import sys
n = int(input())
a=list(map(int,input().split()))
b=[0 for i in range(n)] #玉を入れていく配列
for i in range(n-1,-1,-1): #大きい方から見ていく
    limit=n//(i+1) #倍率の限界値
    if limit==1: #限界値が１、つまりその数自身しか参照しない場合
        b[i]=a[i] #玉を入れるかの判断はa[i]にしか依らない
    else:
        modcontainer=0 #剰余の格納容器
        for j in range(limit,0,-1): #倍率も大きい方からチェック
            modcontainer+=b[(i+1)*j-1] #実際に入っているところを参照
            modcontainer%=2
        if modcontainer!=a[i]:
            b[i]=1
print(b.count(1))
if b.count(1)==0:
    sys.exit()
else:
    c=list(enumerate(b))
    d=[str(i+1) for i in range(len(b)) if c[i][1]==1]
    print(" ".join(d))

Submission status: Accepted

Solution code:
import sys
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()
cnt = [0]*(N+1)
ans = []
M = 0
for i in range(N-1,-1,-1):
  tmp = sum(cnt[i::i+1])
  if tmp%2 != a[i]:
    ans.append(str(i+1))
    cnt[i] = 1
    M += 1

if M == 0:
  print(0)
else:
  print(M)
  print(" ".join(ans))

Submission status: Accepted

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

B = [0] * N
for _ in range(N-1, -1, -1):
    if A[_] == 1:
        if sum(B[_::_+1]) % 2 == 0:
            B[_] = 1
    else:
        if sum(B[_::_+1]) % 2 == 1:
            B[_] = 1
print(sum(B))
for i, _ in enumerate(B):
    if _ == 1:
        print(i+1)

Submission status: Accepted

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

for i in range(N, 0, -1):
    tmp = 0
    j = i
    while j < N+1:
        tmp += A[j]
        j += i
    A[i] = tmp % 2
ans = []
for i, j in enumerate(A):
    if j == 1:
        ans.append(i)

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().strip().split(' ')))
R = [0 for i in range(N+1)]
ans = []

for _ in range(N):
    i = N - _
    a = A[i-1]
    if sum(R[i::i]) % 2 != a:
        R[i] = 1
        ans.append(i)

ans.sort()
print(len(ans))
if ans:
    print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
def main():
    N = int( input())
    A = [0] + list( map( int, input().split()))
    ANS = [0]*(N+1)
    for i in range(N,0,-1):
        t = sum([ANS[i*(j+1)] for j in range(N//i)] )%2
        if t == A[i]:
            continue
        ANS[i] = 1
    print( sum(ANS))
    print( " ".join( map( str, [ i for i in range(N+1) if ANS[i] == 1])))
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ans = []
for i, j in enumerate(A):
    if j == 1:
        ans.append(i)
# ans = [i for i, j in enumerate(A) if j == 1]

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

Submission status: Accepted

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

for i in range(N//2, 0, -1):
    tmp = 0
    j = i
    while j < N+1:
        tmp += A[j]
        j += i
    A[i] = tmp % 2
    # A[i] = sum(A[i::i]) % 2
ans = [i for i, j in enumerate(A) if j == 1]

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

Submission status: Accepted

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

for i in range(N//2, 0, -1):
    # tmp = 0
    # j = i
    # while j < N+1:
    #     tmp += A[j]
    #     j += j
    # A[i] = tmp % 2
    A[i] = sum(A[i::i]) % 2
ans = [i for i, j in enumerate(A) if j == 1]

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

Submission status: Accepted

Solution code:
# URL https://refining-process.hatenablog.com/entry/2019/07/21/005322
N = int(input())
a = list(map(int,input().split()))

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

def check(i):
    cnt = 0
    n = i
    while n <= N:
        cnt += b[n-1]
        n += i
    return cnt

for i in range(N-1, -1, -1):
    if (a[i] + check(i+1)) % 2 == 1:
        b[i] = 1

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

print(cnt)
L = [str(int(i)) for i in ans]
print(' '.join(L))

# N = int(input())
# A = list(map(int, input().split()))
# Ab = [0] * N
# for i in range(1,N+1):
#     Ab[i-1] = sum([A[j-1] for j in range(1,N+1) if j % i == 0])
# print(Ab)
# ans = [0] * N
# for i, a in enumerate(Ab[::-1]) :
#     if i <= N / 2:
#         ans[i] = a
#     else :
#     print(a)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for k in range(n, 0, -1):
    cnt = 0
    for x in range(k, n + 1, k):
        cnt += ans[x - 1]
    if cnt % 2 != a[k - 1]:
        ans[k - 1] = 1
m = ans.count(1)
print(m)
if m != 0:
    print(' '.join(map(str, [i + 1 for i, x in enumerate(ans) if x == 1])))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)


# @profile
def resolve():
    N = [int(x) for x in sys.stdin.readline().split()][0]
    a_list = [int(x) for x in sys.stdin.readline().split()]

    logger.debug('{} {}'.format(N, a_list))

    box_list = [0 for _ in range(N)]

    for i in reversed(range(N)):
        suma = sum(box_list[i:N:i+1])

        r = suma % 2
        if r != a_list[i]:
            box_list[i] = 1

    s = sum(box_list)
    print(s)

    if s > 0:
        print(' '.join(
            [str(i + 1) for i in range(len(box_list)) if box_list[i]]))


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
1 0 0"""
        output = """1
1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """5
0 0 0 0 0"""
        output = """0"""
        self.assertIO(input, output)

Submission status: Accepted

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

ans = [0] * N
for i in range(N,0,-1):
    ts = sum(ans[i-1:N:i])
    if ts % 2 != A[i-1]: ans[i-1] = 1

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

Submission status: Accepted

Solution code:
N = int(input())
arr = [0] + list(map(int, input().split(' '))) #ずらしておく。
for i in range(N//2, 0, -1):
  arr[i] = sum(arr[i::i]) % 2
ans = [i for i, j in enumerate(arr) if j == 1]
print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = [0 for i in range(N)]#玉を収納していくリスト

def check(i):
#Nには箱の番号（aのindex+1)を大きい順に入れる
    n = i
    cnt = 0
    #aaの倍数の箱に入っている玉の数をカウント
    while n <= N:
        cnt += b[n-1]
        n += i
        #aaを2倍、3倍、、、としていく
    return cnt

for i in range(N-1, -1, -1):
    if (a[i]+check(i+1))%2 == 1:
        b[i] = 1
    
ans = sum(b)
ll = []
for i in range(N):
    if b[i] == 1:
        ll.append(i+1)

lll = [str(i) for i in ll]
if ans == 0:
    print(ans)
else:
    print(ans)
    print(" ".join(lll))

Submission status: Accepted

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

C = [0]*(N+1)
ans = []
for i in range(N, 0, -1):
    c = 0
    for j in range(2*i-1, N, i):
        if C[j]:
            c += 1
    if c % 2 != A[i-1]:
        ans.append(i)
        C[i-1] = 1
ans.reverse()
print(len(ans))
if ans:
    print(*ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = [0] + list(map(int, input().rstrip().split()))
    for i in range(n // 2, 0, -1):  # second half: no multiples
        A[i] = sum(A[i::i]) % 2
    ans = [i for i, j in enumerate(A) if j]
    print(len(ans))  # all cells: [1] -> len() (much faster than sum())
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

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



NumValid = [True] * (N+1)
ans = []
NumAns = [0] * (N+1)


for i in reversed(range(1,N+1)):
    j = 2 * i
    tmp = 0
    while j < N+1:
        tmp += NumAns[j]
        j += i
        
    if tmp % 2 == 0:
        if A[i-1] == 0:
            NumAns[i] = 0
        else:
            NumAns[i] = 1
            ans.append(i)
    else:
        if A[i-1] == 0:
            NumAns[i] = 1
            ans.append(i)
        else:
            NumAns[i] = 0
        
print(len(ans))
print(' '.join(map(str,ans)))

Submission status: Accepted

Solution code:
import math
N = int(input())
a_array = list(map(int,input().split()))
ans_array = [] 
now_ball_array = [0] * N

for i in range(N-1,-1,-1):
    if a_array[i] != now_ball_array[i]:
        ans_array.append(str(i+1))
        box_root = math.ceil(math.sqrt(i+1))
        if box_root * box_root == (i+1):
            now_ball_array[box_root-1] = (now_ball_array[box_root-1] + 1) % 2  
        for j in range(1,box_root):
            if (i+1) % j == 0:
                now_ball_array[j-1] = (now_ball_array[j-1] + 1) % 2 
                now_ball_array[(i+1)//j-1] = (now_ball_array[(i+1)//j-1] + 1) % 2  
    # print(now_ball_array)
print(len(ans_array))
if len(ans_array):
    print(" ".join(ans_array))

Submission status: Accepted

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

d = c + a

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

    b[i] = (s ^ d[i])

# print(b)
print(b.count(1) if b.count(1) else 0)
for i in range(1, len(b)):
    if b[i] != 0:
        print(i, end=' ')

Submission status: Accepted

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

d = c + a

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

    b[i] = (s ^ d[i])

# print(b)
print(b.count(1) if b.count(1) else 0)
if len(b):
    for i in range(1, len(b)):
        if b[i] != 0:
            print(i, end=' ')
else:
    print(0)

Submission status: Accepted

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

for i in range(1,n+1)[::-1]:
    ball_sum = sum(balls[i::i]) % 2
    if ball_sum ^ a[i]:
        balls[i] = 1

print(sum(balls))
ball_list = [str(k) for k, v in enumerate(balls) if v == 1 ]
print(" ".join(ball_list))

Submission status: Accepted

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

for i in range(N, 0, -1):
    x = 0
    for j in range(i, N+1, i):
        x ^= a[j]

    a[i] = x

ans = []
for i, ai in enumerate(a):
    if ai == 1:
        ans.append(i)

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

Submission status: Accepted

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

Submission status: Accepted

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

A = [None] + A
B = [None] + [0] * N

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

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 = [int(i) for i in input().split()]
b = [0 for i in range(N)]
c = []


for i in range(N-1, -1, -1):
    for j in [0, 1]:
        b[i] = j
        if sum(b[i::i+1]) % 2 == a[i]:
            break
    else:
        print("-1")
        exit()

M = sum(b)
print(M)

for index, value in enumerate(b):
    if value == 1:
        c.append(index + 1)

ans = ' '.join(map(str, c))
print(ans)

Submission status: Accepted

Solution code:
# from sys import exit, stderr
# from inspect import currentframe
# def debug(*args):
#     names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
#     print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args), file=stderr)
#     return
N = int(input())
a = [int(_) for _ in input().split()]
b = set()
out = []
n = 0
for i in range(N-1, -1, -1):
    if a[i] == 1:
        out.append(i + 1)
        n += 1
        # print(i+1)
        for f in range(1, int((i+1)**0.5)+1):
            if (i+1)%f == 0:
                a[f-1] = 0 if a[f-1] == 1 else 1
                if f != (i+1)//f and f != 1:
                    a[(i+1)//f-1] = 0 if a[(i+1)//f-1] == 1 else 1
    # debug(a)
print(n)
# print(b)
if len(out) > 0:
    for i in range(len(out)):
        print(out[i], end=" ")
    print()

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-



def solve():
  ## input
  N = int(input())
  An = [0] + list(map(int, input().split()))

  ## solve
  Retn = [0 for _ in range(N+1)]
  for i in range(N,0,-1):
    mul = 2
    while i*mul <= N:
      An[i] = An[i]+An[i*mul]
      mul += 1
    An[i] = An[i]%2
  
  M = An.count(1)
  print(M)
  for i,a in enumerate(An):
    if a==1:
      print(i)

solve()

Submission status: Accepted

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

#0～NのN+1個のindexを持っていてこのうち1～Nを使う
#iの倍数を使うので0indexは都合が悪い
#Asの先頭はダミー,Bsは正解の列(ボール有:1、ボール無:0)
As = [-1] + As
Bs = [0 for _ in range(N+1)]

#N,N-1,N-2,...,3,2,1
for i in reversed(range(1,N+1)):
	tmpS = 0
	#iの倍数の箱があれば積み上げる
	for j in range(2*i,N+1,i):
		tmpS += Bs[j]
		
	#合計とAs[i]が異なると、補正するためにBsに1を
	#それ以外は0なのでデフォルトのまま何もしない
	if tmpS % 2 != As[i]:
		Bs[i] = 1

anss = []
#1のindexを抽出とjoinを使うため文字列化
for i in range(N+1):
	if Bs[i] == 1:
		anss.append(str(i))
		
print(len(anss))
print(" ".join(anss))

Submission status: Accepted

Solution code:
#過去にACを出したコードでのテスト
N=int(input())
a=[-1]+[int(i) for i in input().split()]
b=[0 for i in range(N+1)]
for i in range(1,N+1)[::-1]:
    tmp=0
    for j in range(2*i,N+1,i):
        tmp+=b[j]
    if tmp%2!=a[i]:
        b[i]=1
ans=[]
for i in range(N+1):
    if b[i]==1:
        ans.append(str(i))
print(len(ans))
print(" ".join(ans))