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:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = []
    balls_in_multiple = [0 for _ in range(N + 1)]
    count = 0
    for i in range(N, 0, -1):
        if balls_in_multiple[i] % 2 != A[i - 1]:
            ans.append(str(i))
            count += 1
            for j in make_divisors(i):
                balls_in_multiple[j] += 1
    print(count)
    if count > 0:
        print(' '.join(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
N = int(input())
a_list = [0] + list(map(int, input().split()))
result = True
answer_box = [0] * (N+1)
inboxes = []
for i in range(N, 0, -1):
    last_i = i * (N // i)
    count = 0
    for j in range(last_i, i-1, -i):
        count += answer_box[j]
    if (count % 2) != a_list[i]:
        answer_box[i] = 1
        inboxes.append(i)

if(result):
    print(len(inboxes))
    if(len(inboxes) > 0):
        print(" ".join(str(e) for e in inboxes))
else:
    print(-1)

Submission status: Accepted

Solution code:
from math import ceil

n = int(input())

a = [0] + [int(x) for x in input().split()]

c = [0 for i in a]

for i in range(n, 0, -1):
    # satisfy multiples of i
    curr = 0
    for j in range(i, n+1, i):
        curr += c[j]
    if curr % 2 != a[i]:
        c[i] = 1
    else:
        c[i] = 0


x = c.count(1)

print(x)

for i in range(len(c)):
    if c[i] == 1:
        print(i, end=' ')

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = []
lst = [0] * n
for i, x in reversed(list(enumerate(a))):
  if sum(lst[i::i+1]) % 2 != x:
    lst[i] += 1
    b.append(i+1)
print(len(b))
if len(b) > 0:
  print(*reversed(b))

Submission status: Accepted

Solution code:
N = int(input())
a_s = [None] + [int(elm) for elm in input().split(" ")]
bs = [None for _ in range(N+1)]

out_indexs = []
out_num = 0
for val in range(N, 0, -1):
    r = N // val
    tmp = [bs[val*i] for i in range(2, r+1)]
    #print(val, tmp)
    other_sums = sum(tmp) % 2
    if other_sums == a_s[val]:
        bs[val] = 0
    else:
        bs[val] = 1
        out_indexs.append(val)
        out_num += 1

print(out_num)
if out_num >= 1:
    print(" ".join(map(str, out_indexs)))

Submission status: Accepted

Solution code:
N = int(input())
*A, = map(int,input().split())
D = [0]*(N+1)
ans = []
for i in range(N,0,-1):
    if D[i]%2 != A[i-1]:
        ans.append(i)
        for j in range(1,int(i**0.5)+1):
            if i%j==0:
                D[j] += 1
                if i//j != j:D[i//j] += 1
print(len(ans))
print(*ans)

Submission status: Accepted

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

ans = [0]*(N+1)

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

Submission status: Accepted

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

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

    # divisors.sort()
    return divisors

# memo[0]: 1の箱
# memo[N]: N+1の箱
memo = [0] * N
answer = [0] * N
for i in range(N - 1, -1, -1):
    # print(i, a[i], memo[i])
    answer[i] = (a[i] + memo[i]) % 2
    if answer[i] == 1:
        for divisor in make_divisors(i+1):
            memo[divisor - 1] += 1

print(sum(answer))
# print(answer)
print(' '.join([str(i+1) for i, x in enumerate(answer) if x == 1]))

Submission status: Accepted

Solution code:
n = int(input())
a = ['null']
a += list(map(int,input().split()))
b = ['null'] + [0 for _ in range(n)]
for i in range(n):
  k = n - i
  d = n // k
  xor = 0
  for di in range(1,d+1):
    xor ^= b[di * k]
  b[k] = a[k] ^ xor
c = []
csum = 0
for i in range(1,n+1):
  if b[i] == 1:
    c.append(str(i))
    csum += 1
print(csum)
print(' '.join(c))

Submission status: Accepted

Solution code:


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

num = [0 for i in range(N)]
for i in range(N, 0, -1):
        q = N // i
        s = A[i - 1]
        for j in range(2, q + 1):
                s += num[i * j - 1]
                s = s % 2
        num[i - 1] = s

M = sum(num)
print(M)

lst = []
for i in range(N):
        if num[i] == 1:
                lst.append(i+1)
print(' '.join(map(str, lst)))

Submission status: Accepted

Solution code:
n=int(input())
a_list=list(map(int,input().split()))
a_list=[0]+a_list
ans=[0]*(n+1)
count=0
for i in range(n,0,-1):
    temp=0
    c=n//i
    for j in range(2,c+1):
        temp+=ans[i*j]
    if temp%2==a_list[i]:
        ans[i]=0
    else:
        ans[i]=1
        count+=1
print(count)
for i in range(n+1):
    if ans[i]==1:
        print(i,end='')
        print(' ',end='')

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
L=A[::]
for i in range(N//2,0,-1):
    x=N//i
    s=sum([L[i*k-1] for k in range(1,x+1)])%2
    if L[i-1]!=s: L[i-1]=s
print(sum(L))
L=[str(i+1) for i,c in enumerate(L) if c==1]
print(" ".join(L))

Submission status: Accepted

Solution code:
n = int(input())
a=list(map(int, input().split()))
ans = a[:]
for i in range(n)[::-1]:
  if i+1 > n//2:
    continue
  add = 0
  for j in range(n):
    add += ans[(j+2)*(i+1)-1]%2
    if (j+3)*(i+1)-1 > n-1:
      break
  ans[i] = add + ans[i]
  ans[i] %= 2
m = sum(ans)
aa = []
for i in range(n):
  if ans[i]:
    aa.append(i+1)
print(m)
print(" ".join(tuple(map(str,aa))))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
n = getN()
nums = getList()


yaku = [[] for i in range(n + 1)]

for i in range(1, n//2 + 2):
    for j in range(2, n//i + 1):
        yaku[i*j].append(i)

# print(yaku)
ans = [0 for i in range(n)]
# print(nums)
for i in range(n):
    tmp = n - i
    if ans[tmp - 1] != nums[tmp - 1]:
        ans[tmp - 1] = 1
        for y in yaku[tmp]:
            ans[y-1] = (ans[y-1] + 1) % 2
    else:
        ans[tmp - 1] = 0
    # print(tmp, ans)

# print(ans)
pr = [i + 1 for i, x in enumerate(ans) if x == 1]
# print(pr)
print(len(pr))
print(" ".join(list(map(str, pr))))

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))
Bs = [-1] * N
for i in reversed(range(N)):
  a = As[i]
  r = 0
  for j in range(2,N+1):
    j2 = j*(i+1)-1
    if j2 >= N:
      break
    r += Bs[j2]
  b = (r+a)%2
  #print(i, a, r, b)
  Bs[i] = b
#print(Bs)
Cs = []
for i in range(N):
  if Bs[i] == 1:
    Cs.append(str(i+1))
print(len(Cs))
if len(Cs) > 0:
  print(" ".join(Cs))

Submission status: Accepted

Solution code:
N = int(input())
a = [0] + list(map(int, input().split()))
b = [None] * (N+1)
for i in range(N//2+1, N+1):
    b[i] = a[i]
for j in range(1, N//2+1)[::-1]:
    if a[j] == 1:
        t = 0
        for i in range(j+j, N+1, j):
            t ^= b[i]
        if t == 1:
            b[j] = 0
        else:
            b[j] = 1
    else:
        t = 0
        for i in range(j+j, N+1, j):
            t ^= b[i]
        if t:
            b[j] = 1
        else:
            b[j] = 0
for i in range(1, N//2+1):
    t = 0
    for j in range(i, N+1, i):
        t ^= b[j]
    if a[i]^t:
        print(-1)
        quit()
ans = [i for i, v in enumerate(b) if v]
print(len(ans))
if len(ans):
    print(*ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = set()
for i in range(n - 1, -1, -1):
    count = 0
    c = i + 1
    while c < 200000:
        if c in b:
            count += 1
        c += (i + 1)
    if count % 2 != a[i]:
        b.add(i + 1)
print(len(b))
print(" ".join(list(map(str, b))))

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(1, n+1)[::-1]:
        cnt = 0
        j = i
        while j <= n:
            if b[j] == 1:
                cnt += 1
            j += i
        if cnt % 2 != a[i]:
            b[i] = 1
    num = sum(b)
    print(num)
    if num != 0:
        print(' '.join([str(i) for i, bb in enumerate(b) if bb == 1]))


main()

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):
    a = 0
    for j in range(2,N//(i+1)+1):
        a += ans[j*(i+1)-1]
    if a%2!=A[i]:
        ans[i] = 1

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

print(' '.join(ans))

Submission status: Accepted

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

ans = [0] * n
for i, item in enumerate(a[::-1]):
    number = n - i
    total = 0
    for i in range(1, n+1):
        if number * i > n:
            break
        total += ans[number * i - 1]
    if(total % 2 != a[number - 1]):
        ans[number - 1] = 1
ans_num = sum(ans)
print(ans_num)
if ans_num == 0:
    exit()
ret = []
for i, item in enumerate(ans):
    if item == 1:
        ret.append(i+1) 
if len(ans) > 0:
    print(" ".join([str(item) for item in ret]))

Submission status: Accepted

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


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

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

    X = list(filter(lambda i: B[i-1] == 1, range(1, N+1)))

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



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,heapq,math,resource
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def setrlim():
  sys.setrecursionlimit(250000)
  soft,hard = resource.getrlimit(RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  #resource.setrlimit(RLIMIT_STACK, (128*1024*1024,hard))

n = inn()
a = inl()
b = [0] * (n+1)
cnt = 0
for i in range(n,0,-1):
    sum = 0
    for j in range(i*2,n+1,i):
        sum += b[j]
    if sum%2 != a[i-1]:
        b[i] = 1
        cnt += 1
print(cnt)
for i in range(1,n+1):
    if b[i]==1:
        printn(str(i)+' ')
print("")

Submission status: Accepted

Solution code:
N = int(input())
A = [0] + list(map(int, input().split()))
B = [0] * (N + 1)
for i in reversed(range(1, N + 1)):
  s = 0
  for j in range(2, N // i + 1):
    s += B[i * j]
  if s % 2 != 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=list(map(int,input().split()))
l=[0]*n
for i in range(n-1,-1,-1):
    x=l[i:n:i+1]
    if a[i]==x.count(1)%2:
        l[i]=0
    else:
        l[i]=1
print(l.count(1))
ans=[]
for i in range(n):
    if l[i]==1:
        ans.append(i+1)
ans=map(str,ans)
print(" ".join(ans))

Submission status: Accepted

Solution code:
import numpy as np

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

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

arr.reverse()

for i in range(n):
    base = n-i
    sup = n//base
    now = 0
    for j in range(1,sup+1):
        now += ans[base*j-1]
    if now%2 == arr[i]%2:
        ans[base-1]=0
    else:
        ans[base-1]=1



m = sum(ans)
last = [0 for i in range(m)]
index = 0
for i in range(n):
    if ans[i] == 1:
        last[index] = i+1
        index += 1
print(m)
for i in range(m-1):
    print(last[i],end=" ")
if (m > 0):
    print(last[-1])

Submission status: Accepted

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

i = n
while i > 0:
	x[i] = a[i]
	j = 2 * i
	while j <= n:
		x[i] += x[j]
		x[i] %= 2
		j += i
	i -= 1

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

Submission status: Accepted

Solution code:
N = int(raw_input()) + 1
A = [None] + map(int, raw_input().split())

ans = [0 for i in xrange(N)]

#print N, A

for i in range(N - 1, 0, -1):
    ind = i + i
    xor = A[i]
    while ind < N:
        xor ^= ans[ind]
        ind += i
    ans[i] = xor

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
memo = {}
memo[n] = 0
ans = []
for i in range(n)[::-1]:
    tmp = i + 1
    tmp2 = 2 * tmp
    cnt = 0
    while tmp2 <= n:
        cnt += memo[tmp2]
        tmp2 += tmp
    if cnt % 2 == 1 and a[i] == 0:
        ans.append(tmp)
        memo[tmp] = 1
    elif cnt % 2 == 0 and a[i] == 1:
        ans.append(tmp)
        memo[tmp] = 1
    else:
        memo[tmp] = 0
print(len(ans))
print(" ".join(map(str, ans)))

Submission status: Accepted

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

boxes = [0] * N
for i, a in enumerate(reversed(a_s)):
    i = N - i
    if a != sum(boxes[i - 1::i]) % 2:
        boxes[i-1] = 1

print(boxes.count(1))
for i, b in enumerate(boxes, 1):
    if b == 1:
        print(i)

Submission status: Accepted

Solution code:
def solve():
  N = int(input())
  A = [int(i) for i in input().split()]
  B = [ False ] * N
  for i in range(N - 1, -1, -1):
    count = 0
    for j in range(N // (i + 1)):
      if B[(j + 1) * (i + 1) - 1]:
        count += 1
    if count % 2 != A[i]: B[i] = True

  print(B.count(True))
  for i in range(N):
    if B[i]: print(i + 1)

solve()

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = [0]*(N+1)
for i in range(N, 0, -1):
    temp = 0
    for j in range(1, N//i+1):

        temp += b[j*(i)]
    if temp % 2 != a[i-1]:
        b[i] = 1

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

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

Submission status: Accepted

Solution code:
N=list(map(int, input().split()))
N=N[0]
a=list(map(int, input().split()))
b=[0]*(N+1)
ball=0
for i in range(N,0,-1):
    ans=0
    index=i*2
    while index<=N:
        ans+=b[index]
        index+=i
    if ans%2!=a[i-1]:
        b[i]=1
        ball+=1

print(ball)
moji=""
for i in range(1,N+1):
    if b[i]==1:
        moji+=str(i)+" "
print(moji)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = [0]+list(map(int,input().split()))

    res = [0]*(n+1)
    b = []
    for i in range(n,0,-1):
        e = a[i]
        p = 0
        v = i
        while v <= n:
            p += res[v]
            v += i
        if p%2 != e:
            res[i] = 1
            b.append(i)
    print(len(b))
    for e in b:
        print(e,end=' ')

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys  # {{{
import os
import time
import re
from pydoc import help
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
# }}}

# pre-defined{{{
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
ALPHABETS = [chr(i) for i in range(ord('a'), ord('z')+1)]  # can also use string module
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]
from inspect import currentframe
# }}}

def local_input():# {{{
    from pcm.utils import set_stdin
    import sys
    from pathlib import Path
    parentdir = Path(os.path.dirname(__file__)).parent
    inputfile = parentdir.joinpath('test/sample-1.in')
    if len(sys.argv) == 1:
        set_stdin(inputfile)
# }}}

def solve():
    n = int(input())
    a = list(map(int,input().split()))
    a = [0] + a
    
    for i in range(n,0,-1):
        x = 0
        for j in range(1,(n//i) +1):
            x += a[i*j]
        a[i] = x % 2
    
    m = a.count(1)

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

    return 0

if __name__ == "__main__":# {{{
    try:
        local_input()
        def dump(*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=sys.stderr)
    except:
        def dump(*args):
            pass

    solve()

# vim: set foldmethod=marker:}}}

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
N = int(input())
a = inpl()
s = [0]*N
for i in range(N,0,-1):
    s[i-1] = (sum(s[d*i-1] for d in range(2,N//i+1)) + a[i-1])  % 2
print(sum(s))
ans = " ".join([ str(i+1) for i in range(N) if s[i] ])
if len(ans) > 0:
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = [0] * N
for i in range(N - 1, -1, -1):
  ai = A[i]
  for j in range(i, N, i + 1):
    ai ^= B[j]
  B[i] = ai
print(sum(B))
if sum(B):
  print(' '.join([str(i + 1) for i in range(N) if B[i]]))

Submission status: Accepted

Solution code:
def divisors(n):
    ds = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ds.append(i)
            if i != n // i:# and i != 1:
                ds.append(n//i)
    # divisors.sort()
    return ds

n = int(input())
aa = list(map(int, input().split()))
counts = {}
balls = {}


for i in range(len(aa)):
    if aa[i] == 1:
        counts[i + 1] = 1
    else:
        counts[i + 1] = 0

for i in range(n, 0, -1):
    #print(f'i = {i}, counts={counts}')
    if counts[i] % 2 == 0:
        continue
    # put ball in i
    balls[i] = True
    ds = divisors(i)
    for d in ds:
        counts[d] += 1
balls = list(balls.keys())
print(len(balls))
if len(balls) > 0:
    print(' '.join(map(str, balls)))

Submission status: Accepted

Solution code:
import math


def main():
    N = int(input())
    A = [0] + list(map(int, input().split()))
    cnt = [0] * (N+1)
    ans = []
    for i in range(N, 0, -1):
        if cnt[i] != A[i]:
            ans.append(i)
            mx = int(math.sqrt(i))
            for j in range(1, mx+1):
                if i % j == 0:
                    cnt[j] ^= 1
                    if j ** 2 != i:
                        cnt[i // j] ^= 1
    print(len(ans))
    if len(ans):
        print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

balls = [None] + ([0] * N)


def ball_in(i):
    k = 2
    n = 0
    while k * i <= N:
        n += balls[k * i]
        k += 1
    return 0 if n % 2 == A[i] else 1

for i in range(N, 0, -1):
    balls[i] = ball_in(i)

M = 0
B = []
for i, b in enumerate(balls[1:]):
    if b == 1:
        M += 1
        B.append(str(i + 1))

print(M)
print(" ".join(B))

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    a = [0]+list(map(int, input().split()))
    box = [0]*(N+1)
    for i in range(N//2+1, N+1):
        box[i]=a[i]
    for i in range(1, N//2+1)[::-1]:
        res = 0
        for j in range(2, N//i+1):
            res+=box[j*i]
        box[i] = (res+a[i])%2
        
    print(sum(box))
    for i in range(1, N+1):
        if box[i]==1:
            print(i)
solve()

Submission status: Accepted

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

for n in range(N, 0, -1):
    B[n-1] = A[n-1]
    k=n*2
    while k<=N:
        B[n-1] ^= B[k-1]
        k += n

M = sum(B)
print(M)
if M>0:
    print(' '.join( [str(i+1) for i,b in enumerate(B) if b==1] ))

Submission status: Accepted

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

# Nから順に決めていけば必ず決められる
# 見なければいけない数は、N/2, N/3, ... N/N個 = だいたいNlogN

arr = [0] * (N+1)
ans = []
for i in range(N, 0, -1):
  a = (sum(arr[i::i])+A[i]) % 2
  arr[i] = a
  if a:
    ans.append(i)
print(len(ans))
if len(ans):
  print(' '.join(list(map(str, ans))))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()
h = [0]*n
p = []

for i in reversed(range(n)):
    k = i+1
    if k > n/2:
        h[i] = a[i]
        if a[i] == 1:
            p.append(k)
        continue
    s = 0
    for j in range(1,n//k):
        s += h[k*(j+1)-1]
    s %= 2
    if s != a[i]:
        h[i] = 1
        p.append(k)

t = len(p)

print(t)

if t != 0:
    print(' '.join([str(u) for u in p]))

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):
    num = 0
    for j in range(2 * (i + 1), N + 1, i + 1):
        num += B[j - 1]
    if (num & 1) ^ A[i]:
        B[i] = 1
        ans.append(i + 1)

count = len(ans)
print(count)
if count > 0:
    print(' '.join(map(str, ans)))

Submission status: Accepted

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


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


b = []
parity = [0] * (N+1)
for i in range(N, 0, -1):
    if parity[i] != a[i]:
        b.append(i)
        div = calc_div(i)
        for d in div:
            parity[d] = (parity[d] + 1) % 2

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

def divisor(N, B):
    i = 1
    d = []
    while i ** 2 <= N:
        if N % i == 0:
            B[i-1] = (B[i-1] + 1) % 2
            if i ** 2 < N: B[N // i - 1] = (B[N//i - 1] + 1) % 2 
        i += 1
    return 0


def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    B = [0] * N
    ans = []
    M = 0

    for i in reversed(range(N)):
        if B[i] != A[i]:
            divisor(i+1, B)
            M += 1
            ans.append(i+1)

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def set_ball(i):
    index = i
    ball_count = 0
    while(True):
        ball_count += ball_status[index]
        index += i + 1
        if(index  >= N):
            break
    return (ball_count % 2) != a_list[i]

N = int(input())
a_list = list(map(int, input().strip().split()))

ball_status = [0 for i in range(N)]
for i in range(N):
    flag = set_ball(N-1-i)
    if(flag):
        ball_status[N-1-i] = 1
throw_balls = sum(ball_status)
print(throw_balls)
if(throw_balls > 0):
    ans = ""
    for i in range(N):
        if(ball_status[i] == 1):
            ans += str(i+1)
            ans += " "
    print(ans[:-1])

Submission status: Accepted

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

B = [0] * (N + 1)

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

    if tmp % 2 != A[i]:
        B[i] = 1

for i in range(1, N + 1):
    tmp = 0
    for j in range(i, N + 1, i):
        tmp += B[j]
    if A[i] != tmp % 2:
        print(-1)
        exit()

print(sum(B))
ans = []
for i, b in enumerate(B):
    if b == 1:
        ans.append(i)
if len(ans) > 0:
    print(*ans, sep=' ')

Submission status: Accepted

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

from operator import xor
from functools import reduce

B = [0]*N

for i in range(N)[::-1]:
  B[i] = reduce(xor, B[i:N:(i+1)])^A[i]
  
ans = [i+1 for i,b in enumerate(B) if b==1]
print(len(ans))
for a in ans:
  print(a)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__


def main():
    n = int(input())
    a = [0] + [int(x) for x in input().split()]
    b = [0] * (n + 1)

    for i in range(n, 0, -1):
        tot = 0
        for j in range(2 * i, n + 1, i):
            tot += b[j]
        tot %= 2
        b[i] = tot if a[i] == 0 else 1 - tot

    for i in range(1, n + 1):
        tot = 0
        for j in range(i, n + 1, i):
            tot += b[j]
        if tot % 2 != a[i]:
            print(-1)
            return

    res = []
    for i in range(1, n + 1):
        if b[i]:
            res.append(i)

    print(len(res))
    print(*res)


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#iの倍数が書かれたハコの個数が偶数/奇数
N=int(input())
A = [int(i) for i in input().split()]
B = [None]*N
for i in range(N//2,N):
    B[i] = A[i]

for i in range(N//2):
    j = N//2- i #jの倍数(1-indexed)
    B[j-1] = (sum([B[k*j -1] for k in range(2,N//j+1)]) - A[j-1]) %2
ans = [k+1 for k in range(N) if B[k]]
print(len(ans))
print(*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):
    if sum(b[i-1::i])%2 == a[i-1]:
        continue
    else:
        b[i-1] = 1

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

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

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

divs = [[] for _ in range(N + 1)]
for i in range(1, N + 1):
    n = i
    while n + i <= N:
        n += i
        divs[n].append(i)
ans = [0] * (N + 1)
for i in reversed(range(1, N + 1)):
    ans[i] += A[i]
    ans[i] %= 2
    if ans[i]:
        for d in divs[i]:
            ans[d] += 1
            ans[d] %= 2

nums = []
for i, a in enumerate(ans[1:]):
    if a:
        nums.append(i + 1)
print(len(nums))
print(*nums)

Submission status: Accepted

Solution code:
N = int(input())

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

ball = [-1 for i in range(N)]

for i in range(N):
    num=N-i
    s = 0
    for i in range(N//num):
        if ball[(N//num - i)*num-1]!=-1:
            s+=ball[(N//num - i)*num-1]
        else:
            ball[(N//num - i)*num-1]=(a[num-1]-s)%2
ans = []
for i in range(N):
    if ball[i]==1:
        ans.append(i+1)

print(len(ans))
if len(ans)!=0:
    print(*ans)