Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

Constraints

All values in input are integers.

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

a_i is 0 or 1.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

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

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

M
b_1 b_2 ... b_M

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

Sample Input 1

3
1 0 0

Sample Output 1

1
1

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

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

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

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

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

Sample Input 2

5
0 0 0 0 0

Sample Output 2

0

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



Sample input:
3
1 0 0


Sample output:
1
1

Submission status: Accepted

Solution code:
import sys

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

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

    print(len(ans))
    for x in ans:
        print(x, end=' ')


def main():
    N = int(input())
    a = list(map(int, input().split()))
    a.insert(0, [])
    solve(N, a)


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):
    a[i] = sum(a[i::i]) % 2

s = [i for i, b in enumerate(a) if b]
print(len(s))
print(*s)

Submission status: Accepted

Solution code:
import sys

def count(c,num,N):
        x = 0
        for i in range(num*2,N+1,num):
                x += c[i]
        return x%2


N = int(input())
b = input()
a = list(b.split())
a = [int(s) for s in a]
a = [-1] + a
#print(a)
c = [0 for i in range(N+1)]
if max(a) == 0:
        print("0")
        sys.exit()
for i in range(N,0,-1):
        if i > N//2:
                c[i] = a[i]
        else:
                x = count(c,i,N)
                if a[i] != x: c[i] = 1

#print(c[i])
print(sum(c))
f = 1
for i in range(1,N+1):
        if c[i]:
                if f:
                        print("{}".format(i),end="")
                        f = 0
                else: print(" {}".format(i),end="")
print()

Submission status: Accepted

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

ball = [0] * (n//2) + a[n//2:]

for i in reversed(range(n//2)):
    sum_ball = 0
    for j in range(1, n//(i+1)):
        sum_ball += ball[(i+1)*(j+1)-1]
    if sum_ball % 2 != a[i]:
        ball[i] = 1

index = [i+1 for i, x in enumerate(ball) if x == 1]
l = len(index)
print(l)
if l > 0:
    print(" ".join(map(str, index)))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0]*(N+1)
x = []
for n in range(N):
  if (sum(B[::N-n]))%2!=A[N-n-1]:
    B[N-n]=1
    x.append(str(N-n))
print(len(x),'\n',' '.join(x))

Submission status: Accepted

Solution code:
# coding: utf-8

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

boxes = [0] * n

for i in range(n):
    x = n - i - 1
    if A[x]:
        if sum(boxes[k] for k in range(x, n, x+1)) % 2 == 0:
            boxes[x] = 1
    else:
        if sum(boxes[k] for k in range(x, n, x+1)) % 2 == 1:
            boxes[x] = 1
print(boxes.count(1))
if sum(boxes):
    print(' '.join(map(str, (i+1 for i, b in enumerate(boxes) if b == 1))))

Submission status: Accepted

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

M = 0
b = [0 for i in range(N)]
b.insert(0, -1)
for i in reversed(range(1, N + 1)):
    num = 0
    for j in range(1, N // i + 1):
        num ^= b[j * i]
    b[i] = a[i] ^ num

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

Submission status: Accepted

Solution code:
N = int(input())
As = [int(i) for i in input().split(" ")]
Bs = [0 for _ in range(N)]
for i in reversed(range(N)):
  s = 0
  for j in range(i, N, i+1):
    s += Bs[j] 
  Bs[i] = (s % 2) ^ As[i] 
print(len([b for b in Bs if b == 1]))
for i, b in enumerate(Bs):
    if b == 1:
       print(i + 1, end=" ")

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N = int(input())
A = list(map(int, input().split()))

chk = [0]*N

A.reverse()
for i, a in enumerate(A):
    if i+1 <= N//2:
        if a:
            chk[N-i-1] = 1
    else:
        sum_chk = sum(chk[N-i-1::N-i])
        s2 = sum_chk%2
        if a:
            if s2 == 0:
                chk[N-i-1] = 1
        else:
            if s2 == 1:
                chk[N-i-1] = 1

M = sum(chk)
b = [i+1 for i, v in enumerate(chk) if v==1]
print(M)
if M != 0: print(*b)

Submission status: Accepted

Solution code:
N=int(input())
box=[0]*N
ans=[]
a_list=list(map(int,input().split(' ')))
for i in range(N,0,-1):
    sum=0
    for j in range(1,N+1):
        #print("{}:{}".format(i,j))
        if j*i<= N:
            sum+=box[j*i-1]
        else:
            break
    if sum%2 != a_list[i-1]:
        box[i-1]=1
        ans.append(str(i))
sum=0
print(len(ans))
print(" ".join(ans))

Submission status: Accepted

Solution code:
N = int(input())
l = list(map(int,input().split(' ')))
mid = N // 2
MAP = [0]*N
ans_l = []

for i in range(N,0,-1):
    s = N // i + 1
    t = 0
    for j in range(1,N+1):
      if i*j<=N:
        t += MAP[i*j-1]
      else:
        break
    if t%2 != l[i-1]:
        ans_l.append(str(i))
        MAP[i-1] = 1
leng = len(ans_l)
print(leng)
print(" ".join(ans_l))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N = int(input())
A = list(map(int, input().split()))

chk = [0]*N

A.reverse()
for i, a in enumerate(A):
    if i+1 <= N//2:
        if a == 0:
            continue
        else:
            chk[N-i-1] = 1
            continue
    else:
        sum_chk = sum(chk[N-i-1::N-i])
        s2 = sum_chk%2
        if a == 0:
            if s2 == 0:
                continue
            else:
                chk[N-i-1] = 1
                continue
        else:
            if s2 == 0:
                chk[N-i-1] = 1
                continue
            else:
                continue

M = sum(chk)
b = [i+1 for i, v in enumerate(chk) if v==1]
print(M)
if M != 0: print(*b)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
a = [None] + a
a = tuple(a)

ans = set()
cnt = [0] * (n + 1)

for i in range(n, 0, -1):
    if cnt[i] % 2 != a[i] % 2:
        ans.add(i)

        st = set()
        j = 1
        while j * j <= i:
            if i % j == 0:
                st.add(j)
                st.add(i // j)
            j += 1
        for d in st:
            cnt[d] += 1

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

Submission status: Accepted

Solution code:
def get_divisor(n):
    a,b = [],[]
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            a.append(i)
            b.append(n//i)
    if a[-1]==b[-1]:b.pop()
    a.extend(b[::-1])
    return a

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 get_divisor(i):
            D[j]+=1
print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
 
ball = [0] * N
 
 
if a[-1] == 1:
        ball[-1] = 1
 
for i in reversed(range(N-1)):
        tmp = 0
        if i != 0:
                for j in range(i + (i + 1), N, i + 1):
                        #print("i j ", i , j)
                        if (j + 1) % (i + 1) == 0:
                                tmp += ball[j]
        else:
                tmp = sum(ball[1:])
        #print(i+1, tmp, a[i])
        if tmp % 2 != a[i]:
                ball[i] = 1
 
#print(ball)
 
print(sum(ball))
for i in range(N):
        if ball[i] == 1:
                print(i+1, end = " ")

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)):
    if sum(b[i::i])%2!=a[i]:
        b[i]=1
print(sum(b))
for i,j in enumerate(b):
    if j==1:
        print(i,end=' ')

Submission status: Accepted

Solution code:
import math
import copy
import numpy as np

n = int(input())
a = [int(i) for i in input().split()] 
x = a
num_list = []

i = n
while i > math.ceil(n/2):
  if a[i-1] == 1:
    num_list.append(i)
  i -= 1

i = math.ceil(n/2)
while i > 0:
  count = 0
  tmp = [x[i] for i in range(2*i-1, n, i)]
  s = sum(tmp)%2
  if a[i-1] == s:
    x[i-1] = 0
  else:
    x[i-1] = 1
    num_list.append(i)
  i -= 1

l = (len(num_list))

if l == 0:
  print(0)
else:
  print(l)
  print(' '.join([str(n) for n in num_list]))

Submission status: Accepted

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

for i in range(1, N+1)[::-1]:
  s = 0
  for j in range(1, N // i):
    s += box[(j+1)*i]
  if s % 2 != A[i-1]:
    box[i] = 1
    res.append(i)

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

Submission status: Accepted

Solution code:
def get_divisor(n):
    if n==1:return [1]
    a = [1]
    b = [n]
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            a.append(i)
            b.append(n//i)
    if a[-1]==b[-1]:b.pop()
    a.extend(b[::-1])
    return a

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 get_divisor(i):
            D[j]+=1
print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 2  # type: int


import math
import collections


def solve(N: int, a: "List[int]"):
    b = [0]*N
    for i in range(N-1, -1, -1):
        tmp = 0
        for j in range(2, N//(i+1)+1):
            tmp += b[j*(i+1)-1]
        if tmp % MOD == a[i]:
            b[i] = 0
        else:
            b[i] = 1

    c = [i+1 for i, val in enumerate(b) if val % 2 > 0]
    print(len(c))
    if len(c) != 0:
        print(*c, sep=" ")
    return


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:
def add(n):
    return n + 1

if __name__ == "__main__":
    n = int(input())
    buf = input().split()
    a = [int(s) for s in buf]
    
    boxes = [0] * n

    for i in reversed(range(n)):
        pick_boxes = boxes[i::i+1]
        pick_boxes.pop(0)
        if pick_boxes:
            if (sum(pick_boxes) % 2) == a[i]:
                boxes[i] = 0
            else:
                boxes[i] = 1
        else:
            boxes[i] = a[i]

    box_name = [i for i, x in enumerate(boxes) if x == 1]
    box_name = list(map(add, box_name))
    print(len(box_name))
    if len(box_name) != 0:
        box_name = ' '.join(map(str,box_name))
        print(box_name)

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
b=[0 for i in range(N)]
c=[]
A=0
B=0
for i in range(N):
    s=N//(N-i)
    p=1
    while p<=s:
      if b[(N-i)*p-1]==1:
        A+=1
      p+=1
    p=1
    if (A-a[N-1-i])%2==0:
      b[N-1-i]=0
    elif (A-a[N-1-i])%2==1:
      b[N-1-i]=1
    A=0
for i in range(N):
  if b[i]==1:
    B+=1
    c+=[i+1]
c=[c]
print(B)
print(*c[0])

Submission status: Accepted

Solution code:
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

# 約数リスト
def divisors(n):
    d = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            d.append(i)
            if i != n // i:
                d.append(n//i)
    #d.sort()
    return d

def main():
    N = i2n()
    A = i2nn()
    X = [0] * N
    Y = [0] * N
    for i in range(N, 0, -1):
        t = (A[i-1] + X[i-1]) % 2
        if t > 0:
            Y[i-1] = 1
            dd = divisors(i)
            for d in dd:
                X[d-1] += t
    B = []
    for i, y in enumerate(Y):
        if y > 0:
            B.append(i+1)
    M = len(B)
    print(M)
    for i, b in enumerate(B):
        print(b, end=' ')
    print()

main()

Submission status: Accepted

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

if len(set(A)) == 1 and A[0] == 0:
  print(0)
else:
  ans = [0]*N
  ans[N//2:] = A[N//2:]
  for i in range(N//2):
    j = N//2 - i
    check = 0
    for n in range(N//j):
      check += ans[j*(n+1)-1]
    ans[j-1] = 1 if (check%2 != A[j-1]) else 0
  ans = [i for i,x in enumerate(ans) if x==1]
  print(len(ans))
  print(' '.join([str(n+1) for n in ans]))

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
half=int(N/2)
ans=[-1]*N

for i in range(half, N):
    ans[i]=a[i]
for i in range(half-1, -1, -1):
    s=0
    j=i+(i+1)
    while j<N:
        s^=ans[j]
        j+=(i+1)
    ans[i]=s^a[i]

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

Submission status: Accepted

Solution code:
N = int(input())
a_list = [int(x) for x in input().split()]
cnt = 0
b_list = set()
for i in range(len(a_list), 0, -1):
    tmp = 0
    for j in range(i*2, N+1, i):
        tmp ^= (j in b_list)
    if (tmp != a_list[i-1]):
        b_list.add(i)
M = len(b_list)
print(M)
if (M>0):
    print(" ".join([str(b) for b in b_list]))

Submission status: Accepted

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

for i in range(n):
    k = int(n-i-1)
    if a_list[k] != sum(b_list[k::k+1])%2:
        b_list[k] = 1

b_list = [i+1 for i,x in enumerate(b_list) if x ==1]
x = len(b_list)
print(x)
if x != 0:
    print(*b_list)

Submission status: Accepted

Solution code:
#

#

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

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

    ans = [0] * n
    ans[-1] = al[-1]

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

b=[0]*n

for i in range(1,n+1):
    now=n-i+1
    tmp=0
    j=now+now
    while(j<=n):
        if b[j-1]==1:
            tmp+=1
        j+=now
    tmp=tmp%2
    if tmp==a[now-1]:
        pass
    else:
        b[now-1]=1
# print(b)
anscount=0
ans=[]
for i in range(n):
    if b[i]==1:
        anscount+=1
        ans.append(i+1)
print(anscount)
print(" ".join(map(str,ans)))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0]*(N+1)
x = []
 
for n in range(N):
  i = N-n
  BB = B[::i]
  if (sum(BB))%2 == A[i-1]:
    B[i] = 0
  else:
    B[i] = 1
    x.append(str(i))
  
print(len(x))
print(' '.join(x))

Submission status: Accepted

Solution code:
N = int(input())
aN = [ int(i) for i in input().split() ]
bN = [0] * N

for i in range(N, 0, -1):
    if sum(bN[i-1: :i]) % 2 != aN[i - 1]:
        bN[i-1] = 1

print(sum(bN))
if sum(bN) != 0:
    print(*[i+1 for i, b in enumerate(bN) if b == 1])

Submission status: Accepted

Solution code:
n = int(input())
aa = list(map(int, input().split()))
balls = {}
ai = {}
for i in range(len(aa)):
    if aa[i] == 1:
        ai[i + 1] = 1
    else:
        ai[i + 1] = 0


for i in range(n, 0, -1):
    parity = 0
    k = 1
    while k * i <= n:
        if k * i in balls:
            parity ^= 1
        k += 1
    if parity != ai[i]:
        balls[i] = True

print(len(balls))
if len(balls) > 0:
    print(' '.join(map(str, balls)))

Submission status: Accepted

Solution code:
import math

N = int(input())
a = list(map(int,input().split()))
b = []
for n in range(N):
    b.append(0)

def box_sum(a):
    s = 0
    for i in range(1,a):
        s = s + b[(i+1)*(N-k)-1]
    return s

for k in range(N):
    c = N//(N-k)
    if c==1:
        b[N-1-k] = a[N-1-k]
    else:
        s = box_sum(c)
        if s%2==a[N-1-k]%2:
            b[N-1-k] = 0
        else:
            b[N-1-k] = 1
print(b.count(1))
box_num = [i for i,x in enumerate(b) if x == 1]
for d in range(b.count(1)):
    print(box_num[d]+1)

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 = i+1
    cnt = 0
    for j in range(i+num,N,num) :
        cnt += B[j]
    
    if A[i] != cnt % 2 :
        ans.append(i+1)
        B[i] = 1
    
print(len(ans))
print(*ans, sep="\n")

Submission status: Accepted

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

ball = [0] * N
ans = []

for i in range(1, N+1) :
    ballCount = sum(ball[N-i::N-i+1])
    if ballCount % 2 == A[N-i] :
        pass
    else :
        ball[N - i] = 1
        ans.append(N - i + 1)
print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:

n = int(input())
a = list(map(int, input().split()))
b = [0]*n
cnt = 0
ans = 0
seq = []
for i in reversed(range(1,n+1)):
    sumi = sum(b[i-1:n:i])
    if sumi % 2 == a[i-1]:
        continue
    else:
        b[i-1] = 1
        seq.append(i)
        cnt += 1
    
if ans == -1:
    print(-1)
else:
    print(cnt)
    print(' '.join(list(map(str, seq))))

Submission status: Accepted

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


for i in range((n//2+1),n+1):
  b[i]=a[i]
for i in range(n//2,0,-1):
  j=2
  b[i]=a[i]
  while(j*i<=n):
    b[i]^=b[j*i]
    j+=1

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

Submission status: Accepted

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

st = int(n/2)
ans =  [i+st+1 for i, n in enumerate(a[st:]) if n ==1] 
for ind in range(st, 0, -1):
    tmp = [ls[i] for i in range(2*ind-1, n, ind)]
    s = sum(tmp)%2
    if a[ind-1] == s:
        ls[ind-1] = 0
    else:
        ls[ind-1] = 1
        ans.append(ind)
        
print(sum(ls))
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
l = []
counter = 0
ans_list = []

n = int(input())
b_list = [0 for _ in range(n)]
l = list(map(int, input().split()))

for i in range(n,0,-1):
    index = n // i
    if index == 1: # 倍数がないとき
        b_list[i-1] = l[i-1]
    else:
        sum = 0
        for j in range(2, index+1):
            sum = sum + b_list[(i * j)-1]
        #print(l[i-1], sum)
        if l[i-1] != sum % 2:
            b_list[i-1] = 1

    if b_list[i-1] == 1:
        counter += 1
        ans_list.append(str(i))

#print(ans_list)
print(counter)
if ans_list != []:
    print(' '.join(sorted(ans_list)))

Submission status: Accepted

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

for n in range(N):
  i = N-n
  BB = B[::i]
  if (sum(BB))%2 == A[i-1]:
    B[i] = 0
  else:
    B[i] = 1
    x.append(str(i))
  
if len(x) == 0:
  print(0)
else:
  print(len(x))
  print(' '.join(x))

Submission status: Accepted

Solution code:
import math
def func1(lst, value):
    return [i+1 for i, x in enumerate(lst) if x == value]
N = int(input())
a = list(map(int,input().split()))

b = [0] * N
# half = math.ceil(N/2)
summ = 0
for i in reversed(range(N)):
# print(i)
    x = N//(i+1)
# print("x",x)
    if x == 1:
        b[i] = a[i]
    else:
        for j in range(x):
            # print(j)
            summ += b[(i+1)*(j+1)-1]
        # summ -= a[i]
        # print("sum=",summ)
        judge=summ%2
        # print("judge",judge)
        if (judge==0 and a[i]==0) or (judge==1 and a[i]==1):
            b[i] = 0
        else:
            b[i] = 1
        summ = 0
        judge = 0
# print(b)
print(sum(b))
if sum(b) != 0:
    ans = func1(b,1)
    # print(ans)
    if len(ans)>1:
        ans = map(str,ans)
        print(" ".join(ans))
    else:
        print(str(ans.pop()))

Submission status: Accepted

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

for i in range(1,n+1):

    j = 1
    while (n-i+1)*j <= n:
        B_sum[n-i+1] += B[(n-i+1)*j]
        j += 1
    if B_sum[n-i+1] % 2 != A[n-i]:
        B[n-i+1] = 1
        count += 1
print(count)
for i in range(1,n+1):
    
    if B[i]==1:
        print(str(i) + " ", end = "")

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)):
    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:
m = int(input())
b = list(map(int, input().split()))
a = [-1 for i in range(m)]

for i in range(m//2+1,m+1):
        a[i-1] = b[i-1]

for i in range(m//2,m//3,-1):
    if b[i-1] == b[i*2-1]:
        a[i-1] = 0
    else:
        a[i-1] = 1



for i in range(m//3,0,-1):
#     print(i,a)
    suma = b[i*2-1]
    for ii in range(i*3-1,m,i*2):
        suma += a[ii]
#         print(ii,suma)
    if b[i-1] == suma%2:
        a[i-1] = 0
    else:
        a[i-1] = 1

print(a.count(1))
c= []
for i in range(m):
    if a[i] == 1:
        c.append(str(i+1))

print(' '.join(c))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math

def add_ball(idx):
    add_list = []
    for j in range(1, int(math.sqrt(idx))+1):
        if idx%j == 0:
            add_list.append(j)
            if j != idx//j:
                add_list.append(idx//j)
    for k in add_list:
        b_list[k] += 1

if __name__ == "__main__":
    input = sys.stdin.readline

    n = int(input())
    a_list = list(map(int, input().split()))
    b_list = [0] * (n+1)
    cnt = 0
    ans_list = []
    for a, i in zip(reversed(a_list), range(n, 0, -1)):
        if a != b_list[i]%2:
            cnt += 1
            ans_list.append(i)
            add_ball(i)
    ans_list.sort()
    print(cnt)
    if cnt > 0:
        print(' '.join(map(str, ans_list)))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()] 
#print(a)
b = [0] * n
#print(b)
for i in range(0, n)[::-1]:
  if (i+1)*2 > n:
    if a[i] == 1:
      b[i] = 1
  else:
    tmp = 0
    for j in range(i,n)[::i+1]:
     # print(i, j)
      tmp = tmp ^ b[j]
    b[i] = tmp ^ a[i]
#print(b)
print(sum(b))
for i in range(n):
  if b[i] == 1:
    print(i+1, end=" ")

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
if n==1:
    print(l[0])
    if l[0]==1:print(1)
    exit()
ans=[0]*(n//2)+l[n//2:n]
for i in range(n//2-1,-1,-1):
    s= sum([ans[j] for j in range((i+1)*2-1,n,i+1)])%2
    ans[i]=(l[i]+s)%2
lans=[]
for i in range(n):
    if ans[i]==1:lans.append(i+1)
print(sum(ans))
if sum(ans)>0:print(*lans)

Submission status: Accepted

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

res = [-1 for i in range(N//2)] + [ai for ai in a[N//2 : N]]

for i in range(N//2, 0, -1):
    res[i-1] = (sum(res[2*i-1:N:i]) % 2) ^ a[i-1]

ans = [i+1 for i in range(N) if res[i] == 1]
print(len(ans))

if len(ans) != 0:
    print(' '.join(list(map(str,ans))))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=[0] * N
ans = []
for i in reversed(range(1, N+1)):
    a = 0
    for j in range(1, N+1):
        tmp = i * j
        if tmp > N:
            break
        a = (B[tmp-1] + a) % 2
    if (A[i-1] + a) % 2 == 1:
        ans.append(i)
    B[i-1] = (A[i-1] + a) % 2
print(len(ans))
for a in ans: print(a)

Submission status: Accepted

Solution code:
# Setup
import sys
sys.setrecursionlimit(4100000)
n = int(input())
a = [int(i) for i in input().split()]
balls = [0] * (n+1)

for i in reversed(range(1,n+1)):
    temp = i*2
    current = 0
    while temp <= n:
        current += balls[temp]
        temp += i
    if current%2 == 0:
        if a[i-1] == 0:
            balls[i] = 0
        else:
            balls[i] = 1
    else:
        if a[i-1] == 1:
            balls[i] = 0
        else:
            balls[i] = 1
counter = 0
# if balls[1
for i in range(n):
    if balls[i+1] == 1:
        counter += 1
print(counter)
for i in range(n):
    if balls[i+1] == 1:
        print(i+1)
# print(balls)

Submission status: Accepted

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

b=[0]*N
#Nから0まで1ずつ減らしていく
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:
N = int(input())
A = list(map(int, input().split()))
B = [0]*N
for i in range(N, 0, -1):
  t = B[(i-1)::i]
  s = sum(t)%2
  B[i-1] = 0 if s == A[i-1] else 1

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

Submission status: Accepted

Solution code:


def solve(A, N):
    B = [0] * len(A)
    for i in range(1, N+1)[::-1]:
        A2 = A[i*2] if i*2 <= N else 0
        x = A[i]
        for j in range(i*2, N+1, i):
            x ^= B[j]
        B[i] = x
    return B

#from random import randint
#solve([0] + list(randint(0, 1) for _ in range(1000)), 1000)
def main():
    N = int(input())
    A = [0] + [int(x) for x in input().split()]
    B = solve(A, N)
    print(sum(B))
    for i in range(1, N+1):
        if B[i]:
            print(i)

main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=[0] * N
ans = []
for i in reversed(range(1, N+1)):
    a = A[i-1]
    for j in range(1, N+1):
        tmp = i * j
        if tmp > N:
            break
        a += B[tmp-1]
    if a % 2 == 1:
        ans.append(i)
    B[i-1] = a % 2
print(len(ans))
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0 for _ in range(N)]
for n, a in enumerate(reversed(A)):
    l = N - 1 - n
    if sum(B[l:: l + 1]) % 2 != a:
        B[l] = 1
M = sum(B)
print(M)
ans = [str(n + 1) for n in range(N) if B[n] == 1]
print(' '.join(ans))

Submission status: Accepted

Solution code:
import sys

N = int(input())
Atmp = [0] + list(map(int, input().split()))
A = {}

for i,a in enumerate(Atmp):
    A[i] = a

#print(A)

X = {}

for i in reversed(list(range(1,N+1))):
    Xsum = 0
    j = 2
    while(i*j <= N):
        Xsum += X[i*j]
        j += 1
        continue
    odd = Xsum % 2
    if odd == A[i]:
        X[i] = 0
    else:
        X[i] = 1
    
M = 0
for i in range(1, N+1):
    if X[i] == 1:
        M += 1

print(M)
if M == 0:
    sys.exit()

xxx = []
for i in range(1, N+1):
    if X[i] == 1:
        xxx.append(str(i))

print(' '.join(xxx))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A.insert(0, 0)

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

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

Submission status: Accepted

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

for i in range(0,n):
    j = n - 1 - i
    c = 0
    for k in range(2, n+1):
        idx = k * (j + 1) - 1
        if  idx > n-1:
            break
        c += bn[idx]
    
    bn[j] = (c + ai[j]) % 2


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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

b=[0]*n
m=[]
for i in range(n,0,-1):
    v=0
    for j in range(i,n+1,i):
        v+=b[j-1]
    #b[i-1]=1 if v%2!=a[i-1] else 0
    if v%2!=a[i-1]:
        b[i-1]=1
        m.append(i)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A.insert(0, 0)

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

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