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:
m = int(input())
num_list = list(map(int,input().split()))
ans_list = [0]*m
print_list = []
for i in range(m,0,-1):
    if num_list[i-1] == 0:
        cnt = 0
        for j in range(2,m//i+1):
            cnt += ans_list[i*j-1]
        if cnt % 2 == 1:
            ans_list[i-1] = 1
            print_list.append(i)
    elif num_list[i-1] == 1:
        cnt = 0
        for j in range(2,m//i+1):
            cnt += ans_list[i*j-1]
        if cnt % 2 == 0:
            ans_list[i-1] = 1
            print_list.append(i)
            
if not print_list:
    print(0)
    
else:
    print(sum(ans_list))
    print(*print_list)

Submission status: Accepted

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

ans = [0 for _ in range(n)]
for i in reversed(range(n)):
  tmp = 0
  for j in range((i+1)*2-1,n,i+1):
    if ans[j] == 1:
      tmp += 1
  if a[i] == 0 and tmp % 2 == 1:
    ans[i] = 1
  elif a[i] == 1 and tmp % 2 == 0:
    ans[i] = 1

c = 0
l = []
for i in range(n):
  if ans[i] == 1:
    l.append(i+1)
    c += 1
if c == 0:
  print(0)
else:
  l = [str(i) for i in l]
  l = " ".join(l)
  print(c)
  print(l)

Submission status: Accepted

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

for i in range(N,0,-1):
    c = 0
    for j in range(i,N+1,i):
        c += ans[j]
    if (A[i-1] == 0 and c % 2 == 1) or (A[i-1] == 1 and c % 2 == 0):
        ans[i] = 1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import functools

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

bucket=[0] * (N+1)
parent=[[] for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(i, N+1, i):
        if j != i:
            parent[i].append(j)
#print(parent)

for i in range(N//2+1, N+1):
    bucket[i]=a[i-1]
#print(bucket)

for i in range(N//2, 0, -1):
    bucket[i] = a[i-1] ^ functools.reduce(lambda x, y:x^y, [bucket[val] for val in parent[i]])
#print(bucket)

ans = [str(i) for i, v in enumerate(bucket) if v == 1]
print(len(ans))
print(' '.join(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):
    total = 0
    for j in range(i*2, n+1, i):
        total += b[j - 1]
    if total % 2 == a[i - 1]:
        b[i-1] = 0
    else:
        b[i-1] = 1

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

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
res = [0]*n
for i in range(n,0,-1):
  k = 2
  c = True
  while i*k <= n:
    if res[i*k-1] == 1:
      c = not c
    k += 1
  if c == a[i-1]:
    res[i-1] = 1
print(sum(res))
for i in range(n):
  if res[i]:
    print(i+1,end=" ")

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
A=[0]*N
B=[]
for i in range(N//2,N):
    if a[i]==1:
        A[i]=1
        B.append(i+1)
for i in range(N//2)[::-1]:
    asum=0 
    x=i+1
    for j in range(i,N,x):
        asum=asum+A[j]
    if asum%2!=a[i]:
        A[i]=1
        B.append(i+1)
count=sum(A)
print(count)
if count!=0:
    print(*B)

Submission status: Accepted

Solution code:
n = int(input())
a = [0] + list(map(int, input().split()))
b = [0] * (n+1)
for i in range(n, 0, -1):
  x = 0
  for k in range(1, n//i + 1):
    x += b[i*k]
    #print(i, k, i*k)
  b[i] = 0 if x%2 == a[i] else 1
#print(b)
ans = [i for i in range(n+1) if b[i] == 1]
#print(ans)
print(len(ans))
if len(ans) > 0:
  print(' '.join([str(a) for a in ans]))

Submission status: Accepted

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

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

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

possible = True
for i in reversed(range(1,N//2+1)):
    s = 0
    for j in range(2,int(N/i)+1):
        s = (s+b[i*j]) % 2
    if b[i] == None:
        b[i] = (a[i] + s) % 2
    elif b[i] != (a[i] + s) % 2:
        possible = False
        break

if possible:
    Ans = []
    for i in range(1,N+1):
        if b[i] == 1:
            Ans.append(str(i))
    print(len(Ans))
    ans = " ".join(Ans)
    if ans != "":
        print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
cnt = [0]*(n+1)
ans = []
for i in range(n,0,-1):
    a = A[i-1]
    s = 0
    for j in range(1,n//i+1):
        idx = i*j
        s+=cnt[idx]

    if s%2==0:
        cnt[i] = a
    else:
        cnt[i] = 1-a

    if cnt[i] ==1:
        ans.append(i)
m = sum(cnt)

print(m)
print(*ans)

Submission status: Accepted

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

Submission status: Accepted

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

m = 0
aa = [0] * n
b = []

for i in range(n-1, -1, -1):
    t = sum(aa[i::i+1]) % 2
    if t != a[i]:
        m += 1
        aa[i] += 1
        b.append(i+1)

print(m)
print(*b)

Submission status: Accepted

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

cond = [0] * (N+1)
ans = [0]* (N+1)


def yakusu(x):
    yakusu = [1]
    for i in range(2, int(x**0.5)+1):
        if x%i == 0:
            yakusu.append(i)
            if i != x//i:
                yakusu.append(x//i)
    
    return yakusu

for i in range(N, 0, -1):
    tmp = cond[i]
    if tmp != a[i-1]:
        ans[i] = 1
        cond[i] = 1 - tmp
        if i > 1:
            for j in yakusu(i):
                cond[j] = 1 - cond[j]

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

if res == 0:
    print(0)
else:
    print(res)
    print(' '.join(map(str, reslist)))

Submission status: Accepted

Solution code:
mod = 10**9 + 7
from collections import deque

def main():
    N = iip(False)
    A = iip(True)

    result = [0] * (N+2)
    ans = []

    for i in range(N, 0, -1):
        #s = sum(result[i::i])
        s = 0
        for j in range(1000000):
            if i*j > N+1:
                break
            s += result[i*j]

        if s % 2 != A[i-1]:
            result[i] = 1


    print(sum(result))

    #print(result)
    for i, res in enumerate(result):
        if res == 1:
            ans.append(i)
    split_print_space(ans)


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))

def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        #print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <=0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        #print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod-2)

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod = 10**9 + 7
from collections import deque

def main():
    N = iip(False)
    A = iip(True)

    result = [0] * (N+2)
    ans = []

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


    print(sum(result))

    #print(result)
    for i, res in enumerate(result):
        if res == 1:
            ans.append(i)
    split_print_space(ans)


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))

def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        #print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <=0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        #print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod-2)

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#ABC134-D
if True:
    N=int(input())
    A=[int(i) for i in input().split()]
    fact=[[1] for i in range(N)]
    for i in range(2,N+1):
        k=2
        while k*i<=N:
            fact[k*i-1].append(i)
            k+=1
    # print(fact)
    SUM=[0 for i in range(N)]
    ANS=[]
    for i in reversed(range(N)):
        if (i+1)*2>N:
            if A[i]==1:
                ANS.append(i+1)
                SUM[i]=A[i]
            for j in fact[i]:
                SUM[j-1]=(SUM[j-1]+A[i])%2
        else:
            if SUM[i]==1:
                if A[i]==1:
                    continue
                else:
                    ANS.append(i+1)
                    SUM[i]=1
                    for j in fact[i]:
                        SUM[j-1]=(SUM[j-1]+1)%2
            else:
                if A[i]==0:
                    continue
                else:
                    ANS.append(i+1)
                    SUM[i]=1
                    for j in fact[i]:
                        SUM[j-1]=(SUM[j-1]+1)%2
    print(len(ANS))
    print(' '.join(map(str,ANS)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    N = Scanner.int()
    A = Scanner.map_int()
    B = [0] * N
    for i in reversed(range(N)):
        j = 1
        p = 0
        while True:
            n = j * (i + 1) - 1
            if n >= N:
                break
            p += B[n]
            j += 1
        if A[i] != p % 2:
            B[i] += 1
    ans = sum([b > 0 for b in B])
    print(ans)
    if ans > 0:
        for i, b in enumerate(B):
            if b == 1:
                print(i + 1, end=' ')
        print('')


def main():
    # sys.stdin = open("sample.txt")
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=[-1 for _ in range(n)]
for i in range(n):
  j=n-i
  if n//j<2:
    ans[j-1]=a[j-1]
  else:
    p=sum(ans[2*j-1::j])
    ans[j-1]=abs(a[j-1]-p)%2
b=[0 for _ in range(sum(ans))]
i=0
#print(ans)#######
m=sum(ans)
for j in range(n):
  if ans[j]!=1 and ans[j]!=0:
    print(-1)
    exit()
  if ans[j]==1:
    b[i]=j+1
    i+=1

print(m)
print(*b)

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

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

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

def main():
    N = int(input())
    A = input_nums()
    idx = [i for i in range(1, N+1)]
    A = dict(zip(idx, A))
    B = dict(zip(idx,[0]*N))
    for i in reversed(range(1,N+1)):
        b = i
        cnt = 0
        while b <= N:
            cnt += B[b]
            b += i
        if not cnt % 2 == A[i]:
            B[i] = 1
    sumv = sum(B.values())
    print(sumv)
    if sumv != 0:
        print(*[k for k, v in B.items() if v == 1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

def main():
    N = int(input())
    A = input_nums()
    idx = [i for i in range(1, N+1)]
    A = dict(zip(idx, A))
    B = dict(zip(idx,[0]*N))
    for i in reversed(range(1,N+1)):
        b = i
        cnt = 0
        while b <= N:
            cnt += B[b]
            b += i
        if not cnt % 2 == A[i]:
            B[i] = 1
        else:
            B[i] = 0
    ans = []
    for k, v in B.items():
        if v == 1:
            ans.append(k)
    print(len(ans))
    if len(ans) != 0:
        print(*ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

n=int(input())
l=tuple(map(int,input().split()))
ret=[]
ll=[0]*n
ans=0
for i in range(n,0,-1):
    s=l[i-1]
    for j in range(2,n//i+1):
        s-=ll[j*i-1]
        s%=2
    ll[i-1]=s
    ans+=s
    if s:ret.append(i)
print(ans)
if ans:print(*ret,sep=" ")

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
l=tuple(map(int,input().split()))
ret=[]
ll=[0]*n
ans=0
for i in range(n,0,-1):
    s=l[i-1]
    for j in range(2,n//i+1):
        s-=ll[j*i-1]
        s%=2
    ll[i-1]=s
    ans+=s
    if s:ret.append(i)
print(ans)
if ans:print(*ret,sep=" ")

Submission status: Accepted

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

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

print(sum(b))

for i, j in enumerate(b):
    if j == 1:
        print(i+1)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    res = []
    #dp[i]:i番目の箱に入ってるかどうか
    dp = [0]*n

    #iの倍数の箱を調べる
    for i in range(n, 0, -1):
        #調べる箱列挙
        t = 0
        for j in range(i, n+1, i):
            t += dp[j-1]
        if t%2 != a[i-1]:
            res.append(i)
            dp[i-1] = 1

    if not 1 in a:
        print(0)
    else:
        print(len(res))
        print(*res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    res = []
    #dp[i]:i番目の箱に入ってるかどうか
    dp = [0]*n

    #iの倍数の箱を調べる
    for i in range(n, 0, -1):
        #調べる箱列挙
        t = 0
        for j in range(i, n+1, i):
            t += dp[j-1]
        if t%2 != a[i-1]:
            res.append(i)
            dp[i-1] = 1

    if not 1 in a:
        print(0)
    else:
        if len(res)>0:
            print(len(res))
            print(*res)
        else:
            print(-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import ceil

N = int(input())
D = ceil(N/2)
A = [0] + [int(i) for i in input().split()]

boxes = [0] * (N+1) # 1-indexed

for i in range(D, N+1):
    boxes[i] = A[i]

for i in range(N-D, 0, -1):
    c = 0
    for j in range(i+i, N+1, i):
        if boxes[j]:
            c ^= 1
    if c==A[i]:
        boxes[i]=0
    else:
        boxes[i]=1

res = set()
for i in range(1, N+1):
    if boxes[i]:
        res.add(i)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 28 18:39:26 2020

@author: Kanaru Sato
"""

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

for i in range(0,n):
    givenindex = n-1-i
    given = givenindex+1
    givenl = []
    
    for j in range(1,n+1):
        if given*j <= n:
            givenl.append(given*j)
        else:
            break
        
    sum = 0
    for j in givenl:
        sum += ans[j-1]
        
    if sum%2 == a[givenindex]:
        ans[givenindex] = 0
    else:
        ans[givenindex] = 1

sum = 0
for i in range(n):
    sum = sum + ans[i]
print(sum)

filledbox = []
for i in range(n):
    if ans[i] == 1:
        filledbox.append(i+1)
tmp = " ".join(map(str,filledbox))
print(tmp)

Submission status: Accepted

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

def main():
    n = int(input())
    lis = list(map(int, input().split()))
    val = [0] * n

    for i in range(n, 0, -1):
        if n // i == 1:
            val[i - 1] = lis[i - 1]
        else:
            a = sum(val[i - 1::i])
            if a % 2 != lis[i - 1]:
                val[i - 1] ^= 1

    print(sum(val))
    print(*[i + 1 for i in range(n) if val[i] == 1], sep=" ")
if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(n, 0, -1):
    if n // i == 1:
        val[i - 1] = lis[i - 1]
    else:
        a = sum(val[i - 1::i])
        if a % 2 == lis[i - 1]:
            val[i - 1] = 0
        else:
            val[i - 1] = 1

print(sum(val))
print(*[i + 1 for i in range(n) if val[i] == 1], sep=" ")

Submission status: Accepted

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

for i in range(n, 0, -1):
    if n // i == 1:
        val[i - 1] = lis[i - 1]
    else:
        p = n // i
        a = 0
        for j in range(p):
            a += val[i * (j + 1) - 1]
        if a % 2 == lis[i - 1]:
            val[i - 1] = 0
        else:
            val[i - 1] = 1

t = sum(val) % 2
if lis[0] == t:
    print(sum(val))
    print(*[i + 1 for i in range(n) if val[i] == 1], sep=" ")
else:
    print(-1)

Submission status: Accepted

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

for i in range(N, 0, -1):
  if i>N//2:
    ans[i-1]=A[i-1]
  else:
    X=i+i
    now=0
    while X<=N:
      now+=ans[X-1]
      X+=i
    if now%2==A[i-1]:
      ans[i-1]=0
    else:
      ans[i-1]=1
      
      
print(sum(ans))
for i,a in enumerate(ans):
  if a==1:
    print(i+1, end=" ")

Submission status: Accepted

Solution code:
# とっかかりを掴むために、全探索で実験してみる
n = int(input())
A = list(map(int, input().split()))
boxes = [None]*(n+1)
for i in range(n, 0, -1):
    coef = 1
    tmp = 0
    while i*(coef+1) <= n:
        coef += 1
        tmp += boxes[i*coef]
    boxes[i] = A[i-1] ^ (tmp % 2)

ans = []
for idx, v in enumerate(boxes):
    if v == 1:
        ans.append(idx)

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
nli = list(range(n))[::-1]
bli = [0]*n

for i in nli:
    num = 2
    ball = 0
    while (i+1)*num<=n:
        ball += bli[(i+1)*num-1]
        num += 1
    if ball%2 == a[i]:
        bli[i]=0
    else:
        bli[i]=1

print(bli.count(1))

for i in range(n):
    if bli[i]:
        print(i+1)

Submission status: Accepted

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

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

Submission status: Accepted

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

box = [0]*M
for i in range(M)[::-1]:
    s = sum(box[i::i +1])
    if s % 2 != a[i]:
        box[i] = 1
M = sum(box)
print(M)
if M != 0:
    for i, j in enumerate(box):
        if j == 1:
            print(i + 1)

Submission status: Accepted

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

boxes = [0]*N
for i in range(N)[::-1]:
  s = sum(boxes[i::i+1])
  if s % 2 != A[i]:
    boxes[i] = 1

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

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
B=[0]*n
for i in range(n):
    now=(n-i)*2
    cnt=A[n-i-1]
    while now<=n:
        cnt+=B[now-1]
        now+=n-i
    if cnt%2==1:
        B[n-i-1]=1
print(sum(B))
for i in range(n):
    if B[i]:
        print(i+1,end=" ")

Submission status: Accepted

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

    # divisors.sort()
    return divisors

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

a_list.reverse()

cnt_list = [0] * (2 * (10 ** 5) + 1)
ret = [0] * (2 * (10 ** 5) + 1)

for i in range(len(a_list)):
    if (a_list[i] == 1 and cnt_list[n-i] % 2 == 0) or (a_list[i] == 0 and cnt_list[n-i] % 2 == 1):
        ret[n-i] = 1
        div_list = make_divisors(n-i)
        for div in div_list:
            if cnt_list[div] == 0:
                cnt_list[div] = 1
            else:
                cnt_list[div] = 0

m = ret.count(1)
print(m)
for i in range(n+1):
    if ret[i] == 1:
        print(i)

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(j) for j in input().split()]
#template
#issueから始める
N = int(input())
a = inputlist()
ans = [0]*(N+1)
flag = [0]*(N+1)
def divisore(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(reverse=True)
    return divisors
for i in range(1,N+1):
    k = N+1-i
    d = N//k
    if d == 1:
        ans[k] = a[k-1]
        if a[k-1] == 1:
            li = divisore(k)
            for j in range(len(li)):
                x = li[j]
                flag[x] +=1
    else:
        if flag[k] % 2== a[k-1]:
            ans[k] = 0
        else:
            ans[k] = 1
            lia = divisore(k)
            for s in range(len(lia)):
                y = lia[s]
                flag[y] +=1
ansa = ans[1:]
count = 0
lis = []
for i in range(N):
    if ansa[i] == 1:
        count+=1
        lis.append(i+1)
if count == 0:
    print(0)
    exit()
print(count)
print(*lis)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
for i in range(n-1,-1,-1):
  s=sum(a[i::i+1])
  if s%2!=a[i]:
    a[i]=1-a[i]
print(a.count(1))
print(*[i+1 for i,x in enumerate(a) if x])

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
M=0
X=[]
XX=[0]*N
for i in range(N-1,-1,-1):
  _=0
  for j in range(i+1,N+1,i+1):
    _+=XX[j-1]
  if A[i]==0 and _%2==1:
    M+=1
    X.append(i+1)
    XX[i]=1
  elif A[i]==1 and _%2==0:
    M+=1
    X.append(i+1)
    XX[i]=1
print(M)
print(*X)

Submission status: Accepted

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

l = [0] * (n + 1)

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

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

print(m)
print(*b)

Submission status: Accepted

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

A=[0]*N
sum=0
b=[]

for i in range(N,0,-1):
    #print(i)
    count=0
    for j in range(i-1,N,i):
        count+=A[j]
    if count%2==a[i-1]:
        pass
    else:
        A[i-1]=1
        sum+=1
        b.append(i)

print(sum)
if len(b)!=0:
    print(" ".join(map(str,b)))

Submission status: Accepted

Solution code:
n = int(input())
a=list(map(int,input().split()))
for i in range(n - 1, -1, -1):
    s = sum(a[i ::i + 1])
    if s % 2 != a[i]:
        a[i] = 1 - a[i] # 1 -> 0 , 0 -> 1
print(a.count(1))
print(*[i+1 for i,x in enumerate(a) if x])

Submission status: Accepted

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

half = N // 2

ball = np.zeros(N, dtype=np.bool)
ball[half:] = A[half:]

for i in range(half - 1, -1, -1):
    a = A[i]
    cnt = np.count_nonzero(ball[i:: i + 1]) % 2
    if a != cnt:
        ball[i] = True

ans = np.where(ball == True)[0]
print(len(ans))

if len(ans) > 0:
    print(" ".join([str(x+1) for x in ans]))