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,math,collections,itertools
input = sys.stdin.readline

N = int(input())
a = list(map(int,input().split()))
a.insert(0,0)
b = []
c = [0 for _ in range(N+1)]
for i in range(N,0,-1):
    cnt = 0
    for j in range(2*i,N+1,i):
        if c[j] == 1:
            cnt +=1
    if (cnt%2==1 and a[i] == 0) or (cnt%2==0 and a[i] == 1):
        b.append(i)
        c[i] = 1
print(len(b))
print(*b)

Submission status: Accepted

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

ans = [None]*(N//2) + aa[N//2:]

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

p = sum(ans)
print(p)
if p:
    print(*(i+1 for i,v in enumerate(ans) if v))

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)
    return divisors

B = [0]*N
for i in range(N):
    X = N-i
    P = B[X-1]
    Q = A[X-1]
    if P==Q:
        B[X-1] = 0
    else:
        XDL = make_divisors(X)
        for XD in XDL:
            if XD==X:
                B[XD-1] = 1
            else:
                B[XD-1] = 1 - B[XD-1]
out = []
cnt = 0
for i in range(N):
    if B[i]==1:
        out.append(i+1)
        cnt+=1
print(cnt)
if len(out)>0:
    print(*out)

Submission status: Accepted

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

bits = [0] * (N + 1)

i = N
while i > 0:
    j = i
    ones = 0
    while j <= N:
        ones += bits[j]
        j += i
    if ones % 2 != A[i - 1]:
        bits[i] = 1
    i -= 1

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

print(len(indexes))
if indexes:
    print(*indexes)

Submission status: Accepted

Solution code:
from copy import deepcopy

N=int(input())
A=list(map(int,input().split()))
ans=[0]*(N//2+1)+A[N//2:]
A=[0]+A

ok=1
for i in range(N//2,0,-1):
  if sum(ans[i*2:i*(N//i)+1:i])%2==0:
    ans[i]=A[i]
  else:
    ans[i]=1-A[i]

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

print(len(ans2))
if len(ans2)>0:print(*ans2)

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

N=int(input().rstrip('\n'))
As = [int(x) for x in input().rstrip('\n').split()]
res = [0]*N
for i in range(N,0,-1):
  now = sum(res[i-1::i])%2
  if now!=As[i-1]:
    res[i-1] += 1
print(sum(res))
print(*[x+1 for x in range(N) if res[x]>0])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    q=deque()
    l=[0]*(N+1)
    # for i in range(N,N//2,-1):
    #     if a[i-1]==1:
    #         l[i-1]=1

    #         q.appendleft(i)
    
    for i in range(N,0,-1):
        tot=0
        for j in range(2,N+1):
            if i*j>N:
                break
            tot^=l[(i*j)]
            
        if tot!=A[i-1]:
            l[i]+=1
            q.appendleft(i)
    print(len(q))
    if q:
        print(*q)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
aaa = list(map(int, input().split()))
M = 0
bbb = [0] * (N + 1)
for i in range(N, 0, -1):
    if (aaa[i-1] + sum(bbb[i::i])) % 2 == 1:
        M += 1
        bbb[i] = 1
print(M)
if M > 0:
    ans = [i for i, b in enumerate(bbb) if b]
    print(*ans)

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

if sum(ans) == 0:
    print(0)
    exit()

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = [0] * N
index = []
M = 0
for i in range(N-1,-1,-1):
    a = ans[i:N:i+1]
    if sum(a) % 2 == A[i]:
        ans[i] = 0
    else:
        ans[i] = 1
        index.append(i+1)
        M += 1
print(M)
print(*index[::-1])

Submission status: Accepted

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

import numpy as np
B = [0 for _ in range(n)]
ans = []
for i, a in enumerate(A[::-1]):
  i = len(A) - i - 1
  B[i] = int(np.array(B[i::i+1]).sum() % 2 != a)
  if B[i] == 1:
    ans.append(i+1)
print(len(ans))
if len(ans) > 0:
  print(*ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int,input().split()))
    ans = [-1 for i in range(n)]
    for i in range(n):
        c = n//(n-i)
        if c<2:
            if a[n-1-i] == 1:
                ans[n-1-i] = 1
            else:
                ans[n-1-i] = 0
        else:
            s = 0
            for j in range(2,c+1):
                s += ans[j*(n-i)-1]
            ans[n-i-1] = (s+a[n-1-i])%2 
    a = []
    for i in range(n):
        if ans[i] == 1:
            a.append(i+1)
    if len(a)==0:
        print(0)
    else:
        print(len(a))
        print(' '.join(list(map(str,a))))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
bits = list(map(int,input().split()))
ans = set()
for i in reversed(range(n)):
  for j in range(i+(i+1),n,i+1):
    bits[i] ^= bits[j]
  if bits[i] == 1:
    ans.add(i+1)
print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().rstrip()


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

    for i in range(N, 0, -1):
        j = 2
        count = 0
        while i * j <= N:
            count += B[i * j]
            j += 1
        if (count + A[i]) % 2 == 0:
            pass
        else:
            B[i] = 1
    print(sum(B))

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().rstrip()


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

    for i in range(N, 0, -1):
        j = 2
        count = 0
        while i * j <= N:
            count += B[i * j]
            j += 1
        if (count + A[i]) % 2 == 0:
            pass
        else:
            B[i] = 1
    print(sum(B))

    for i in range(len(B)):
        if B[i]==1:
            print(i)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    a = tuple(map(int, input().split()))

    b = []
    box = [0] * (N + 1)
    for i, r in zip(reversed(range(1, N + 1)), a[::-1]):
        total_r = sum(box[j] for j in range(i, N + 1, i)) % 2
        if r == 0 and total_r == 1:
            box[i] = 1
            b.append(i)
        elif r == 1 and total_r == 0:
            box[i] = 1
            b.append(i)

    M = len(b)
    if M == 0:
        print(0)
    else:
        print(M)
        print(" ".join(map(str, b)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    b = []
    box = [0] * (N + 1)
    for i, r in zip(reversed(range(1, N + 1)), a[::-1]):
        total_r = sum(box[j] for j in range(i, N + 1, i)) % 2
        if r == 0 and total_r == 1:
            box[i] = 1
            b.append(i)
        elif r == 1 and total_r == 0:
            box[i] = 1
            b.append(i)

    M = len(b)
    if M == 0:
        print(0)
    else:
        print(M)
        print(" ".join(map(str, b)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
A = list(map(int, input().split()))
box = [0] * (N+1)
M = 0
ans = deque()

for i in range(N, 0, -1):
    tmp = 0
    for j in range(i*2, N+1, i):
        tmp += box[j]
    tmp = tmp % 2
    if tmp != A[i-1]:
        box[i] = 1
        M += 1
        ans.appendleft(i)

if M == 0:
    print(0)
else:
    print(M)
    print(*ans)

Submission status: Accepted

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

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

if M == 0:
    print(0)
else:
    ans = ans[::-1]
    print(M)
    print(*ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=[0]*n
for i in range(n):
    num1=n-i
    num2=0
    for j in range((n//num1)-1):
        num2+=ans[num1*(j+2)-1]
    num2%=2
    ans[-1-i]=(num2+a[-1-i])%2
print(ans.count(1))
ans2=[]
for i in range(n):
    if ans[i]==1:
        ans2.append(i+1)
if len(ans2)!=0:
    print(*ans2)

Submission status: Accepted

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

def main(n,a):
    a.insert(0,0)
    b=[0]*(n+1)
    for i in range(n,0,-1):
        sum=0
        j=i*2
        while(j<=n):
            sum+=b[j]
            j+=i
        b[i]=(a[i]-(sum%2)+2)%2
    #print(b)
    ans=[]
    for i in range(1,n+1):
        if b[i]!=0:
            ans.append(i)
    return ans

if __name__=='__main__':
    n,a=readinput()
    ans=main(n,a)
    print(len(ans))
    if len(ans)>0:
        print(' '.join(map(str,ans)))

Submission status: Accepted

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

Submission status: Accepted

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

b = [-1] * n
for i in range(n, 0, -1):
    cnt = sum(b[j - 1] for j in range(i + i, n + 1, i))
    b[i - 1] = int(a[i - 1] != cnt % 2)

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

Submission status: Accepted

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

def cnt_rem(ans, x):
    i = 2
    ret = 0
    while (x + 1) * i <= n:
        ret += ans[(x + 1) * i - 1]
        i += 1
    
    return ret % 2

for i in range(n - 1, -1, -1):
    cnt = cnt_rem(ans, i)
    if cnt != a[i]:
        ans[i] += 1

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

Submission status: Accepted

Solution code:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
a = [0] + LIST()
b = [0]*(n+1)

for i in range(n, 0, -1):
    j = i + i
    tmp = 0
    while j <= n:
        tmp += b[j]
        j += i
    if tmp % 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:
import math
import collections

def main():
    n = int(input())
    a=[int(i) for i in input().split()]

    #0 < i < N+1 の iについて、iの倍数が書かれた箱に入ってるボールの個数を2で割った余りがai
    # 1 <= N < 2*10**5
    good = [0]*(n+1)
    for i in range(n//2+1,n+1):
        good[i] = a[i-1]
    for i in range(n//2,0,-1):
        tmp = 0
        odd_even = a[i-1]
        for j in range(i+i,n+1,i):
            tmp += good[j]
        if(odd_even!=tmp%2):
            good[i] = 1

    print(sum(good))

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Created: Jul, 13, 2020 08:25:55 by Nobody
# $Author$
# $Date$
# $URL$
__giturl__ = "$URL$"


from sys import stdin
input = stdin.readline


def main():
  N = int(input())
  A = [-1]+list(map(int, input().split()))

  D = [-1]*(N+1)
  for i in range(N, 0, -1):
    if i > int(N/2):
      D[i] = A[i]
    else:
      temp_sum = 0
      for j in range(N//i, 1, -1):
        temp_sum += D[i*j]
      D[i] = (temp_sum % 2) ^ A[i]

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


if(__name__ == '__main__'):
  main()

Submission status: Accepted

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

for i in reversed(range(1,n+1)):
  d=n//i-1
  e=0
  for j in range(2,d+2):
    
    if b[i*j]%2==1:e+=1#
  if (a[i]==0 and e%2==1) or (a[i]==1 and e%2==0):
    b[i]=1
    c+=1
print(c)
b2=[i+1 for i in range(n) if b[i+1]>0]
print(*b2 if len(b)>0 else "")

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):
  s=0
  t=i
  while t<=n:
    s+=b[t]
    t+=i
  if s%2==a[i]:
    pass
  else:
    b[i]=1
ans=0
c=[]
for i,bb in enumerate(b):
  if bb>0:
    ans+=bb
    c.append(i)
if ans>0:
  print(ans)
  print(*c)
else:
  print(0)

Submission status: Accepted

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

ans = []
b = [0]*n
for i in range(n-1,-1,-1):
    if sum(b[i::i+1])%2 == 1:#iから最後までをi+1個おきに
        if a[i] == 0:
            b[i] += 1
            ans.append(i+1)
    else:
        if a[i] == 1:
            b[i] += 1
            ans.append(i+1)

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N = I()
    A = LI()
    B = [0] * N

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

        B[i - 1] = tmp ^ A[i - 1]

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import sqrt, ceil

n = int(input())
data = list(map(int, input().split()))
balls = []

mid = n//2+1
table = [0] * n
for idx in range(mid-1, n):
    table[idx] = data[idx]
    if data[idx] == 1:
        balls.append(idx+1)
for idx in range(mid-2, -1, -1):
    score = 0
    for idx2 in range(idx, n, idx+1):
        score += table[idx2]
    if score%2 != data[idx]:
        table[idx] = 1
        balls.append(idx+1)

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

Submission status: Accepted

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

B = [0]*n
ans = []

for i in range(n-1,-1,-1):
    if sum(B[i::i+1])%2!=A[i]:
        B[i] = 1
        ans.append(i+1)
print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N = ri()
A = rl()

def get_divs(n):
	m = n**0.5
	divs = set()
	i = 1
	while i <= m:
		if n % i == 0:
			divs.add(i)
			divs.add(n//i)
		i += 1
	return divs

B = [0] * N

R = [0] * N
for i in range(N-1, -1, -1):
	if R[i] % 2 == A[i]:
		B[i] = 0
	else:
		B[i] = 1
		n = i+1
		for v in get_divs(n):
			R[v-1] += 1

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

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N = ri()
A = rl()

B = [0] * N

R = [0] * N
for i in range(N-1, -1, -1):
	if R[i] % 2 == A[i]:
		B[i] = 0
	else:
		B[i] = 1
		n = i+1
		j = 1
		while j*j <= n:
			if n % j == 0:
				R[j-1] += 1
				m = n//j
				if m != j:
					R[m-1] += 1
			j += 1

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

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


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


# 実装を行う関数
def resolve(test_def_name=""):
    m = int(input())
    b_s = list(map(int, input().split()))

    divisors = [[0]] + [make_divisors(i) for i in range(1, m + 1)]
    ans = [0] + [0 for i in range(1, m + 1)]
    count = [0] + [0 for i in range(1, m + 1)]

    for num, b in reversed(list(enumerate(b_s, start=1))):
        if (b == 1 and count[num] % 2 == 0) or (b == 0 and count[num] % 2 != 0):
            ans[num] = 1
            for div in divisors[num]:
                count[div] += 1

    # 結果比較
    # if b_s != ans:
    #     print(-1)
    #     return
    ans = ans[1:]
    print(ans.count(1))

    if ans.count(1) == 0:
        return

    aaa = []
    for cnt, i in enumerate(ans, start=1):
        if i == 1:
            aaa.append(cnt)

    print(*aaa)

    # テストクラス


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

    def test_input_1(self):
        test_input = """3
1 0 0"""
        output = """1
1"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """5
0 0 0 0 0"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """5
1 0 0 0 1"""
        output = """1
5"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """5
0 0 0 0 1"""

        output = """2
1 5"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

N = INT()
a = [0] + LIST()
ans = [0]*(N+1)

for i in range(N, 0, -1):
	tmp = 0
	for j in range(N//i, 1, -1):
		if ans[i*j] == 1:
			tmp ^= 1
	if a[i] != tmp:
		ans[i] = 1


ans = [idx for idx, x in enumerate(ans) if 0 < x]
print(len(ans))
print(*ans)

Submission status: Accepted

Solution code:
import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

B = [-1 for _ in range(N)]
ans = []

for i in range(N, 0, -1):
    tmp_sum = 0
    tmp_i = 2 * i
    while N >= tmp_i:
        tmp_sum += B[tmp_i - 1]
        tmp_i += i

    if A[i-1] == tmp_sum % 2:
        B[i-1] = 0
    else:
        ans.append(i)
        B[i-1] = 1

print(len(ans))
if len(ans):
    print(" ".join(map(str, ans[::-1])))

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    a = LI()

    b = [0] * N
    for i in range(N):
        # (N-1-i)*2以降を全部足したのをaから引く
        tmp = 0
        for j in range(N - 1 - i, N, N - i):
            tmp ^= b[j]
        b[N-1-i] = tmp ^ a[N-1-i]

    m = b.count(1)
    print(m)
    if m >= 1:
        ans = []
        for i, e in enumerate(b):
            if e == 1:
                ans.append(i + 1)
        print(*ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    a = LI()

    b = [0] * N
    is_ok = True
    for i in range(N):
        if N // (N - i) == 1:
            b[N-1-i] = a[N-1-i]
        else:
            # (N-1-i)*2以降を全部足したのをaから引く
            tmp = 0
            for j in range(N - 1 - i, N, N - i):
                tmp += b[j]
            b[N-1-i] = (tmp + a[N-1-i]) % 2

    m = b.count(1)
    print(m)
    if m >= 1:
        ans = []
        for i, e in enumerate(b):
            if e == 1:
                ans.append(i + 1)
        print(*ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

B = [-1 for _ in range(N)]
ans = []

for i in range(N, 0, -1):
    tmp_sum = 0
    tmp_i = 2 * i
    while N >= tmp_i :
        tmp_sum += B[tmp_i - 1]
        tmp_i += i

    # print(i, tmp_sum)
    if A[i-1] == tmp_sum % 2:
        B[i-1] = 0
    else:
        ans.append(i)
        B[i-1] = 1

print(len(ans))
if len(ans):
    print(" ".join(map(str, ans[::-1])))

Submission status: Accepted

Solution code:
def m():
    N = int(input())
    A = [0] + list(map(int, input().split()))
    X = [0] * (N+1)
    for i in range(N, 0,-1):
        p = 0
        for j in range(i, N+1, i):
            if X[j]: p +=1
        if p % 2 != A[i]:
            X[i] = 1
    M = X.count(1)
    print(M)
    for i in range(1, N+1):
        if X[i] == 0:
            continue
        print(i, end=' ')
    return

m()

Submission status: Accepted

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


ans = set()
for i in range(n-1, -1, -1):
  for j in range(i+1,n+1,i+1):
    if j in ans:
      a[i] += 1
  if a[i]%2 == 1:
    ans.add(i+1)
print (len(ans))
print (*ans)

Submission status: Accepted

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

box = [0] * (N + 1)

for i in range(N, 0, -1):
    cnt = 0
    for j in range(i*2, N+1, i):
        cnt += box[j]
    if cnt%2 != alist[i-1]:
        box[i] = 1

M = sum(box)
ans = []
for i in range(1, N+1):
    if box[i]:
        ans.append("{}".format(i))

print(M)
print(" ".join(ans))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
a = np.array(list(map(int,input().split())), dtype=int)
b = np.zeros(n, dtype=int)

for i in range(n-1, -1, -1):
    m = sum(b[i::i+1]) % 2
    b[i] = (a[i] + m) % 2
bsum =sum(b) 
if bsum == 0:
    print(bsum)
else:
    ans = np.where(b>0)[0] + 1
    ans = ans.astype('str')
    print(bsum)
    print(' '.join(ans))

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    B = [0 for _ in range(N)]
    ans = [] 
    for i in range(N, 0, -1):
        cnt = 0
        mul = 2
        while i*mul-1 < N:
            cnt += B[i*mul-1]
            mul += 1
        if A[i-1] == cnt%2:
            B[i-1] = 0
        else:
            B[i-1] = 1
            ans.append(i)
    print(len(ans))
    if len(ans) != 0:
        print(*ans)

    

if '__main__' == __name__:
    resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
b=[]
dp=[0]*(N+1)
ans=0
for i in range(N,0,-1):
  p=0
  for j in range(1,N//i+1):
    p+=dp[j*i]
  if p%2!=a[i-1]:
    dp[i]=1
    ans+=1
    b.append(i)
b.sort()
print(ans)
print(*b)

Submission status: Accepted

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

for i in range(n)[::-1]:
    m = n//(i+1)
    count = 0
    for j in range(1, m+1):
        count += ball[j*(i+1)-1]
    ball[i] = (a[i]%2)^(count%2)

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