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
sys.setrecursionlimit(10**6)

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

B = [-1]*N
for j in range(N//2 + 1,N+1):
    B[j-1] = A[j-1]

def rec(i):
    if B[i-1] != -1:
        return B[i-1]
    res = A[i-1]
    for j in range(2*i,N+1,i):
        res -= rec(j)
        res %= 2
    B[i-1] = res
    return res

rec(1)
b = [i for i in range(1,N+1) if B[i-1] == 1]
M = len(b)

print(M)
if b != []:
    print(*b)

Submission status: Accepted

Solution code:

N = int(input())
a = [int(i) for i in input().split()]
b = [0 for i in range(N)]

a = [0] + a
b = [0] + b

m = N // 2

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

if len(ans) == 0:
    print(0)
else:
    print(len(ans))
    for i in range(len(ans)):
        if i == 0:
            print(ans[i], end="")
        else:
            print(" ", end="")
            print(ans[i], end="")

Submission status: Accepted

Solution code:
n = int(input())
a = [int(a) for a in input().split()]
flag = [0] * (n + 1)
ret = []
for i in range(n, 0, -1):
    if flag[i] ^ a[i - 1] == 1:
        ret.append(i)
        j = 1
        while j * j <= i:
            if i % j == 0:
                flag[j] ^= 1
                if j * j != i:
                    flag[i // j] ^= 1
            j += 1
print(len(ret))
if len(ret) > 0:
    print(" ".join(map(str, ret)))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)
B = [0] * (N + 1)
for i in range(N, 0, -1):
  j = i * 2
  s = 0
  while (j <= N):
    s += B[j]
    j += i
  B[i] = (s + A[i]) % 2
print(sum(B))
if sum(B) > 0:
  ans = ''
  for i in range(1, N + 1):
    if B[i] == 1:
      ans += str(i) + ' '
  print(ans.strip())

Submission status: Accepted

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

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

Submission status: Accepted

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

# 逆から解く
balls = [0]*N
for i in range(N-1, -1, -1):
    # 存在する限り、倍数の箱に入っているボールの数を取得する
    ball_sum = 0
    box_i = i + 1
    while box_i <= N:
        # print("{} is counted. i:{}, box_i:{}".format(i + 1, i, box_i))
        ball_sum += balls[box_i - 1]
        box_i += i +1 # 次の倍数
        
    # 偶数奇数に一致するようにボールを入れる
    rest = ball_sum % 2
    
    if checks[i] == 0:
        # 偶数にしたいとき
        if rest == 1:
            balls[i] = 1
    
    if checks[i] == 1:
        # 奇数にしたいとき
        if rest == 0:
            balls[i] = 1

print(sum(balls))
print(" ".join([str(i + 1) for i in range(0, N) if balls[i] == 1]))

Submission status: Accepted

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

ans = a[:]

for i in reversed(range(n)):
    ans[i] = sum(ans[i :: i + 1]) % 2

print(sum(ans))
print(*[i + 1 for i in range(n) if ans[i]])

Submission status: Accepted

Solution code:
import sys
p = [[int(t) for t in r.split()] for r in sys.stdin.read().split('\n') if r != '']
N = p[0][0]
a = p[1]
b = [0]*N
c = 0
for i in range(N, 0, -1):
    f = a[i-1] ^ (sum(b[i-1:N:i]) % 2)
    b[i-1] = f
    c += f
print(c)
print(' '.join([str(i + 1) for i, n in enumerate(b) if n]))

Submission status: Accepted

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

def find_baisu(a, N):
    j = 2
    ret = []
    while(a*j <= N):
        ret.append(a*j)
        j += 1
    return ret
    
for i in range(N):
    num = N-i
    baisu = find_baisu(num, N)
    baisu_box_sum = 0
    for j in range(len(baisu)):
        baisu_box_sum += box[baisu[j]]
    if(baisu_box_sum % 2 == a[num]):
        box[num] = 0
    else:
        box[num] = 1

M = 0
ans = ''
for i in range(N+1):
    if(box[i] == 1):
        M += 1
        ans += str(i) + ' '

print(M)
print(ans)

Submission status: Accepted

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

hako = [0]*(N+1)

for i in range(N, 0, -1):
    cnt = 0
    j = i
    x = j
    while j <= N:
        cnt += hako[j]
        j += x
    
    if cnt%2 != A[i]:
        hako[i] = 1


print(hako.count(1))
s = ""
for i, x in enumerate(hako):
    if x == 1:
        s += str(i) + " "

print(s)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
INL=LI()
RES=[0]*(N+1)
cnt = 0
for i in range(N, 0, -1):
    pt = 2*i
    sm = 0
    while pt <= N:
        sm += RES[pt]
        pt += i
    if (not sm & 1 and INL[i-1]) or (sm & 1 and not INL[i-1]):
        cnt += 1
        RES[i] = 1

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
a = LIST()

ball = [0] * (N+1)

for i in range(len(a), 0, -1):
	if i > N // 2:
		ball[i] = a[i-1]
	else:
		tmp = a[i-1]
		for x in range(i, N+1, i):
			# print(x)
			if x == i:
				continue
			tmp = tmp ^ ball[x]
			# print("tmp", tmp)
		ball[i] = tmp
		# print("i",i)
		# print(tmp, a[i-1])
# print(ball)
print(sum(ball))
for i, j in enumerate(ball):
	if j == 1:
		print(i, end=" ")
print()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jul 20 20:53:47 2019

@author: ctiuser
"""


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

counta = 0
Ans = [0 for i in range(N)]
ans = []
for i in range(N,0,-1):
    tmp = N // i
    res = A[i-1]
    for j in range(tmp):
        res ^= Ans[(j+1)*i-1]
    if res == 1:
        Ans[i-1] = 1
        ans.append(i)
        counta += 1

ans.reverse()

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

Submission status: Accepted

Solution code:


from collections import defaultdict
N = int(input())
a = [int(i) for i in input().split()]

d = defaultdict(int)
# balls = [0 for _ in range(N)]

ans = 0
for n in range(N, 0, -1):
    a_i = a[n-1]
    cnt = 0
    n2 = n*2
    while n2 <= N:
        cnt += d[n2]
        n2 += n
    if cnt % 2 != a_i:
        d[n] = 1
        ans += 1

print(ans)
if ans >= 1:
    for k, v in d.items():
        if v == 1:
            print(k)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 2  # type: int

def solve(N: int, a: "List[int]"):
    a = [0] + a
    result = [0 for i in range(N+1)]
    for i in range(N, 0, -1):
        bai = 1

        summation = 0
        while bai * i <= N:
            summation += result[bai * i]
            bai += 1

        if a[i] == 0:
            if summation % 2 == 0:
                result[i] = 0
            else:
                result[i] = 1
        else:
            if summation % 2 == 0:
                result[i] = 1
            else:
                result[i] = 0
                
    print(sum(result))

    if sum(result) > 0:
        output = ''
        for i in range(1, N+1):
            if result[i] == 1:
                output += ' %d' % (i)
        print(output[1:])
    
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
#!/usr/bin/env python3
import sys

MOD = 2  # type: int

def solve(N: int, a: "List[int]"):
    a = [0] + a
    result = [0 for i in range(N+1)]
    for i in range(N, 0, -1):
        count_baisu = 1

        sum_ = 0
        while count_baisu * i <= N:
            sum_ += result[count_baisu * i]
            count_baisu += 1

        if a[i] == 0:
            if sum_ % 2 == 0:
                result[i] = 0
            else:
                result[i] = 1
        else:
            if sum_ % 2 == 0:
                result[i] = 1
            else:
                result[i] = 0
                
    print(sum(result))

    if sum(result) > 0:
        output = ''
        for i in range(1, N+1):
            if result[i] == 1:
                output += ' %d' % (i)
        print(output[1:])
    
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
# -*- coding: utf-8 -*-
"""
Created on Sat Jul 20 21:10:32 2019

@author: yama
"""

n = int(input())
l = [-1] + list(map(int, input().split()))

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

for i in range(n, 0, -1):
    c = n//i
    s = 0
    for j in range(1, c+1):
        s += ll[i*j]
    if l[i] == 0:
        if s % 2 == 0:
            ll[i] = 0
        else:
            ll[i] = 1
    else:
        if s % 2 == 0:
            ll[i] = 1
        else:
            ll[i] = 0
              
m = ll.count(1)
print(m)
lll = []
for i in range(1, len(ll)):
    if ll[i] == 1:
        lll.append(i)
        
print(' '.join(map(str, lll)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
import math
mod = 10**9 + 7
def I(): return int(input())
def II(): return map(int, input().split())
def L(): return list(map(int, input().split()))
def TWO(M):
  L=[0]*M
  R=[0]*M
  for i in range(M):
    L[i],R[i] = II()
  return L, R
N = I()
a = L()
ans = [-1]*(N)
for i in range(N)[::-1]:
  temp = N//(i+1)
  x = []
  for j in range(2,temp+1):
    x.append(ans[(i+1)*j-1])
  ans[i] = abs(a[i]-sum(x)%2)
  #print(i+1, x, ans)

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

Submission status: Accepted

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

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

m = sum(ans)
s = ""
for i in range(n):
    if ans[i] == 1 and s == "":
        s += str(i+1)
    elif ans[i] == 1:
        s += " "+str(i+1)

if m == 0:
    print(m)
else:
    print(m)
    print(s)

Submission status: Accepted

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

for i in range(n,0,-1):
    m=n//i
    total=0
    for j in range(1,m+1):
        if j==1:
            total+=a[i-1]
        else:
            total+=b[i*j-1]
    b[i-1]=total%2
ans=sum(b)
print(ans)
if ans != 0:
    l=[]
    for i in range(n):
        if b[i]==1:
            l.append(i+1)
    print(*l)

Submission status: Accepted

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

Submission status: Accepted

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

m = 0
# あとで先頭削除
b_list = [0 for _ in range(N+1)]

result_list = []

for i in range(N,0,-1):
    tmp = 0
    for j in range(i+i, N+1, i):
#         print(j)
        tmp += b_list[j]
#     print(b_list)
    
    # これまでの結果（右側）とあまりが一致してない時は1にする
    if not tmp%2 == a_list[i]:
        b_list[i] = 1
        result_list.append(i)
        m += 1

print(m)
if m > 0:
    print(" ".join(map(str,result_list)))

Submission status: Accepted

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

for i in range(N, 0, -1):

    j = i
    sum_num = 0
    while j <= N:
        a = a_list[j-1]
        if j != i:
            sum_num += a
        if i == 1:
            j += 1
        else:
            j += i
    if sum_num % 2 == 0:
        if a_list[i-1] == 0:
            continue
        else:
            a_list[i-1] = 1
    else:
        if a_list[i-1] == 1:
            a_list[i-1] = 0
        else:
            a_list[i-1] = 1

ans = sum(a_list)
print(ans)

for i in range(1, N+1):
    if a_list[i-1] != 0:
        print(i)

Submission status: Accepted

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

ans = [-1] * (N+1)
count = 0
for i in range(N, 0, -1):
    tmp = 0
    p = i
    p += p
    # print (i, p)
    while p <= N: #pの倍数について確認
        tmp += ans[p]
        p += i
    ans[i] = abs(a[i] - (tmp%2))
    if ans[i] == 1:
        count += 1
    # print (ans)
    
# print (ans)
print (count)
for i in range(1, N + 1):
    if ans[i] == 1:
        print (i)

Submission status: Accepted

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

b = [0] * N
for i in range(N-1, -1, -1):
    s = 0
    k = i + (i+1)
    while k < N:
        s += b[k]
        k += (i+1)

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

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

Submission status: Accepted

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

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


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

    c = [0] * n
    b = []

    for i in range(n - 1, -1, -1):
        if i < n // 2:
            if (sum(c[j] for j in range(i, n, i + 1)) % 2) != a[i]:
                c[i] = 1
                b.append(i + 1)
        elif a[i]:
            c[i] = 1
            b.append(i + 1)

    print(len(b))
    print(*b)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

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

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

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

def main():
    N = INT()
    A = LIST()
    M = 0
    b = []
    yaku = [0] * N;
    for i in range(N):
        n = N - i
        if (yaku[n-1] + A[n-1]) % 2:
            b.append(n)
            M += 1
            for i in range(1, int(n**0.5)+1):
                if n % i == 0:
                    yaku[i - 1] += 1
                    if i != n // i:
                        yaku[n//i - 1] += 1
    b.reverse()
    print(M)
    if M != 0:
        print(*b)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def prim(n):
    result = []
    for x in range(1, int(n ** 0.5) + 1):
        if n % x == 0:
            result.append(x)
            pair = n // x
            if pair != x:
                result.append(n // x)
    return result

ans = [0] * (n + 1)
ball = [0] * (n + 1)
for i in reversed(range(1, n + 1)):
    value = ans[i] ^ a[i]
    ball[i] = value
    for x in prim(i):
        ans[x] ^= value
print(sum(ball))
for i, v in enumerate(ball[1:], 1):
    if v:
        print(i, end=" ")
print()

Submission status: Accepted

Solution code:
n = int(input())
aa = list(map(int, input().split()))
aa = [-1] + aa[:]
ans = []
for i in range(n // 2 + 1, n + 1):
    if aa[i]:
        ans.append(i)
for i in range(n // 2, 0, -1):
    s = 0
    for ii in range(i * 2, n + 1, i):
        s += aa[ii]
    if aa[i] == s % 2:
        aa[i] = 0
    else:
        aa[i] = 1
        ans.append(i)
print(len(ans))
if ans:
    print(*ans, sep="\n")

Submission status: Accepted

Solution code:
n = int(input())
div = [None] + [int(v) for v in input().split()]
result = [None for _ in range(n+1)]

for d in range(1, n+1):
    for i in range(n//d, n//(d+1), -1):
        part = sum([result[i*j] for j in range(2, d+1)], 0)
        result[i] = (part + div[i]) % 2

print(sum(result[1:]))
for i, r in enumerate(result[1:]):
    if r > 0:
        print(i+1)

Submission status: Accepted

Solution code:
n = int(input())
aaa = list(map(int, input().split()))
aaa = [0] + aaa
for i in range(n // 2, 0, -1):
    b = 0
    j = i * 2
    while n >= j:
        b ^= aaa[j]
        j += i
    aaa[i] ^= b

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

Submission status: Accepted

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

b = [0]
b.extend(a)
array = [0 for _ in range(n+1)]
result = []

for i in range(n, 0, -1):
    num = 1
    counter = 0
    while i*num <= n:
        if array[i*num] == 1:
            counter += 1

        num += 1

    if counter % 2 != b[i]:
        array[i] = 1
        result.append(i)

print(len(result))
for i in result:
    print(i, end=' ')

Submission status: Accepted

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


B = []
checked = [0 for _ in range(N)]
for i in range(N, 0, -1):
    num = N // i
    a = A[i-1]
    for j in range(1, num+1):
        a += checked[j*i-1]
    if a % 2 == 1:
        B.append(i)
        checked[i-1] = 1
print(len(B))
print(' '.join([str(b) for b in B]))

Submission status: Accepted

Solution code:
import math

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

B = [str(N - i) for i in range(math.ceil(N / 2)) if A[N - i - 1] == 1]
C = [0] * math.floor(N / 2) + A[math.floor(N / 2):]

for i in range(math.floor(N / 2), 0, -1):
    count = 0
    for j in range(i, N + 1, i):
        count += C[j - 1]
    if not count % 2 == A[i - 1]:
        B.append(str(i))
        C[i - 1] = 1

print(len(B))
if not len(B) == 0:
    print(" ".join(B))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 
# 1, 2, 3, 4, 5
# sum(a) = a1
# sum(偶数) = a2
# 後ろから
# 
n = int(input())
a = list(map(int, input().split()))

ans = [0]*n
for i in range(n)[::-1]:
    for j in range(0,n+1,i+1)[::-1]:
        if j == 0:
            continue
        if j-1 == i:
            if a[i] == ans[i]:
                ans[i] = 0
            else:
                ans[i] = 1
        else:
            ans[i] = (ans[i] + ans[j-1]) % 2
cnt = sum(ans)
b = []
for i in range(n):
    if ans[i] == 1:
        b.append(i+1)
print(cnt)
if cnt:
    print(*b)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[]
bb=b.append
for i in range(n,0,-1):
    if i>n//2:
        bb(a[i-1])
    else:
        cnt=0
        j=3
        while(True):
            if i*j>n:
                break
            if b[n-i*j]==1:
                cnt+=1
            j+=2
        bb((cnt+a[i-1]+a[i*2-1])%2)
b=list(reversed(b))
print(sum(b))
if sum(b)>0:
    c=[]
    cc=c.append
    for i,j in enumerate(b):
        if j==1:
            cc(str(i+1))
    print(" ".join(c))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

# いっこ入力
n =int(input())

# 空白区切りの数列をリストに代入
a = [int(i) for i in input().split()]

b = [0]*n

for i in range(n-1,(n-1)//2,-1):
    b[i]=a[i]
#print(b)
for i in range(n//2,-1,-1):
    p=a[i]
    for j in range(2*i+1,n,i+1):
        p = (p ^ b[j])
    b[i]=p
#print(b)
ball = 0
for i in range(n):
    ball += b[i]
print(ball)
for i in range(n):
    if b[i]==1:
        print(i+1,end=' ')
print("")

Submission status: Accepted

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

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

Submission status: Accepted

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

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

c = [0] * (N+1)
for i in range(N, 0, -1):
    check_sum = sum(c[::i]) % 2
    if check_sum != a[i-1]:
        c[i] = 1

m = sum(c)
b = [i for i, x in enumerate(c) if x == 1]

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

Submission status: Accepted

Solution code:
def getlist():
	return list(map(int, input().split()))

N = int(input())
a = getlist()
L = [0] * N
ans = []

c = 0
for i in range(N):
	x = int(N // (N - i))
	val = 0
	for j in range(1, x):
		if L[(N - i) * (j + 1) - 1] == 1:
			val += 1
	if val % 2 != a[N - 1 - i]:
		L[N - 1 - i] = 1
		ans.append(N - i)
		c += 1

print(c)
ans = list(map(str, ans))
print(" ".join(ans))

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
a = LI()

b = [0 for i in range(N)]
cnt = 0
for i in reversed(range(N)):
    part_sum = 0
    step_cnt = N // (i+1)
    for step in range(2,step_cnt+1):
        # print("step",step)
        part_sum += b[step * (i+1)-1]
    # print(part_sum)
    b[i] = (part_sum + a[i]) % 2

# print(b)
poss = []
for i in range(N):
    if b[i] == 1:
        cnt += 1
        poss.append(i+1)

print(cnt)
for pos in poss:
    print(pos)

Submission status: Accepted

Solution code:
import sys

fin = sys.stdin.readline
N = [int(elem) for elem in fin().split()][0]
a_list = [int(elem) for elem in fin().split()]


inv_a_list = a_list[::-1]

ball_list = [0 for _ in range(N)]
ball_idx = []
for i, each_a in enumerate(inv_a_list):
    current_idx = N-i
    sup_sum = sum([ball_list[j * current_idx-1] for j in range(2, int(N / current_idx)+1)])
    if (each_a + sup_sum) % 2 == 0:
        continue
    else:
        ball_list[current_idx-1] = 1
        ball_idx.append(str(current_idx))

print(sum(ball_list))

if len(ball_idx) > 0:
    print(' '.join(ball_idx))

Submission status: Accepted

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

  for i in range(n - 1, -1, -1):
    x = sum(v[i::i + 1]) % 2

    if x != a[i]:
      v[i] = 1

  idx = [str(i + 1) for i, x in enumerate(v) if x == 1]

  print(len(idx))

  if len(idx) != 0:
    print(' '.join(idx))


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
def f():
    b = [0] * n
    for i in range(n-1, -1, -1):
        b[i] = a[i] ^ (sum(b[i::i+1]) & 1)
    return b
res = [i+1 for i, x in enumerate(f()) if x > 0]
print(len(res))
print(' '.join(map(str, res)))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

N = int(input().strip())
As = list(map(int, input().strip().split(' ')))
Bs = [0] * N

for i in range(N - 1, -1, -1):
    if i >= N // 2:
        Bs[i] = As[i]
    else:
        Bs[i] = abs(As[i] - (sum(Bs[2 * i + 1::i + 1]) % 2))

M = sum(Bs)
print(M)
if M != 0:
    print(" ".join(str(i+1) for i, b in enumerate(Bs) if b == 1))

Submission status: Accepted

Solution code:
import math

n=int(input())
alist=list(map(int, input().split())) 
blist=[]
for i in range(n):
    blist.append([])

for i in range(n):
    ima=n-i-1
    kosu=math.floor(n/(ima+1))
    nanko=0
    #print(ima, kosu)
    for j in range(kosu-1):
        #nima=(kosu-j-1)*(ima+1)
        nima=(ima+1)*(kosu-j)-1
        #print(nima)
        if blist[nima][0]==1:
            nanko+=1
    nanko=nanko%2
    if alist[ima]==nanko:
        blist[ima]=[0]
    else:
        blist[ima]=[1]

#print(blist)
kotaelist=[]
for bl in range(n):
    if blist[bl]==[1]:
        kotaelist.append(bl+1)

print(len(kotaelist))
for s in kotaelist:
    print(s, end =" ")

Submission status: Accepted

Solution code:
def li():
    return list(map(int, input().split()))


if __name__ == "__main__":
    n = int(input())
    a_list = li()
    box_list = [0] * n
    div = 1
    while n // (div + 1) - 1 >= 0:
        for i in range(n // div - 1, n // (div + 1) - 1, -1):
            value = a_list[i]
            index = (i + 1) * 2 - 1
            while index < n:
                value = value ^ box_list[index]
                index = index + (i + 1)
            box_list[i] = value
            # print(value)
        div = div + 1
    box_sum = sum(box_list)
    box_list[0] = (box_sum % 2) ^ a_list[0]
    print(box_sum + box_list[0])
    for index, box in enumerate(box_list):
        if box == 1:
            print(index + 1, end=" ")

# n // 2 + 1 -- n まではaの通りにボールを入れる
# n // 3 + 1 -- n // 2 まではaと２倍した場所の箱を見てボールを入れる
#

Submission status: Accepted

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

B = [None] * (N+1)

C = []

for i in range(N+1 -1, 1 -1, -1):
  ans = A[i]
  j = i*2
  while j <= N:
    if B[j]:
      ans ^= 1
    j += i
  B[i] = ans
  if ans:
    C.append(i)

print(sum(B[1:]))
print(*C)