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: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(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)]

N = I()
A = LI()

ans = [False] + [bool(a) for a in A]

for i in range(1,N+1)[::-1]:
    judge = bool(A[i-1])
    for j in range(i+i, N+1, i):
        ans[i] ^= ans[j]
    if (judge==ans[i]):
        continue
    else:
        break
else:
    M = sum(ans)
    print(M)
    for i in range(1, N+1):
        if (ans[i]):
            print(i, end=" ")
    if (M>0):
        print()
    quit()

print(-1)

Submission status: Wrong Answer

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


num = int(N // 2 + 1)
cnt = {}
for i in range(1, N + 1):
    cnt[i] = 0
A.reverse()
B = []

for i, a in enumerate(A):
    i = N - i
    if i >= num:
        if a == 1:
            for p in make_divisors(i):
                cnt[p] = (cnt[p] + 1)
            B.append(i)
    else:
        if cnt[i] != a:
            for p in make_divisors(i):
                cnt[p] = (cnt[p] + 1)
            B.append(i)


print(len(B))
B = list(map(str, B))
print(' '.join(B))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
l = [0 for i in range(N)]
ans = []
memo = 0
cnt = 0
for i in reversed(range(N)):
    j = 2
    while (i+1)*j <= N:
        memo += a[(i+1)*j-1]
        j += 1
    memo = memo%2
    if memo != a[i]:
        l[i] = 1
        cnt += 1
        ans.append(str(i+1))
ans.sort()
print(cnt)
print(" ".join(ans))

Submission status: Wrong Answer

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

ball = [False for _ in range(n)]

ans = []
for i, a in enumerate(reversed(box)):
    #print("{} {}".format(i,a))
    idx = n - 1 - i
    count_right = 0
    p = 2
    j = (n - i + 1) * p
    #print("{} {} {}".format(i,a, j))
    while j <= n:
        #print("w {} {}".format(j,n))
        if ball[j-1]:
            count_right += 1
        p+=1
        j = (idx+1) * p
    if a != 0:
        if (count_right % 2) != 0:
            ball[idx] = False
        else:
            ball[idx] = True
            ans.append(idx)
    else:
        if (count_right % 2) != 0:
            ball[idx] = True
            ans.append(idx)
        else:
            ball[idx] = False

ans_len = len(ans)
print(ans_len)
if (ans_len == 0):
    exit
if (ans_len == 1):
    pass
#print(ball)
for i, b in enumerate(ball):
    if b:
        print(i+1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

import sys
from math import ceil

n= int(sys.stdin.readline())
a= [ int(x) for x in sys.stdin.readline().split() ]
print( -1 )

Submission status: Wrong Answer

Solution code:
n = int(input())
li = list(map(int,input().split()))
li = [-1] + li

dp = [-1] * (n+1)
cnt = n
tmp = 0
s = -1

for i in range(1,n+1):
    for j in range(0,n+1,cnt):
        if j == 0:
            continue
        if s == -1:
            s = j
        if dp[-i] == -1:
            dp[-i] = li[j]
        tmp += dp[j]
        #print(i,j,tmp,li[j])
    
    if tmp%2 != li[s]:
        tmp -= dp[-i]
        dp[-i] += (li[j]+1)%2
        tmp += dp[-i]
        if tmp%2 != li[j]:
            print(-1)
            exit()
    cnt -= 1
    tmp = 0
    s = -1

print(dp.count(1))
ans = list([i for i,x in enumerate(dp) if x == 1])
print(*ans)

Submission status: Wrong Answer

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

result = []
for i in range(N):
    if a[i] == 1:
        result.append(i + 1)
M = len(result)
print(M)
if M != 0:
    print(result[0], end = "")
    for i in range(1, M):
        print(" " + str(result[i]), end = "")

Submission status: Wrong Answer

Solution code:
n = int(input())
a = tuple(map(int, input().split()))
b = [0] * n
ret = 0
ret2 = []
append = ret2.append
for i in range(n, 0, -1):
  count = 0
  for j in range(i+i, n+1, i):
    count += b[j-1]
  # print((i, count))
  if not (count % 2) == a[i-1]:
    b[i-1] = 1
    ret += 1
    append(i)

# print(b)
print(ret)
if ret == 0:
  exit()

# print(*reversed(ret2))

for i in range(n-1, -1, -1):
  if b[i] == 1:
    print('%d ' % i, end="")

Submission status: Wrong Answer

Solution code:
import numpy

N = int(input())

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

b = [0 for i in range(N)]

ans = []

# print(a)

l = N//2

for i in range(l+1, N+1):
    b[i-1] = a[i-1]
    if a[i-1] == 1:
        ans.append(i)

ind = l
for _ in range(l):
    # print("ind" , str(ind))
    # print("b")
    # print(b)
    ai = a[ind - 1]
    iter = N // ind - 1
    s = 0
    for j in range(1, iter+1):
        s += b[ind + j * ind - 1]
    # print("s = " + str(s))
    if (s % 2) == ai:
        b[ind - 1] = 0
    else:
        b[ind - 1] = 1
        ans.append(ind)

    if ind == 1:
        break
    else:
        ind -= 1
# print("b")
# print(b)
m = sum(b)
# print("m")
print(m)

if m != 0:
    for c in ans:
        print(c, end ="")

Submission status: Wrong Answer

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

b = [0] * (N + 1)
half = N // 2
b[half + 2:] = A[half + 1:]
for i in range(half, 1, -1):
    s = sum([b[j]for j in range(i * 2, N + 1, i)]) % 2
    if s != A[i]:
        b[i] = 1
s = sum(b)
if s % 2 != A[0]:
    b[1] = 1
    s += 1
print(s)
if s != 0:
    for i, b_ in enumerate(b):
        if b_ == 1:
            print(i, end=" ")

Submission status: Wrong Answer

Solution code:
N=int(input())
a=list(map(int, input().split()))
n=N//2
b=[None]*N
for i in range(n,N):
        b[i]=a[i]
for i in range(n-1,0,-1):
        c=0
        t=i
        while t<N:
                if b[t]==1:
                        c+=1
                t+=i+1
        b[i]=c%2
M=b.count(1)
if a[0]==0:
        b[0]=M%2
else:
        b[0]=M%2+1
if b[0]==1:
        print(M+1)
else:
        print(M)
for i in range(N):
        if b[i]==1:
                print(i+1,end=" ")

Submission status: Wrong Answer

Solution code:
N = int(input())
aArr = list(map(int, input().split()))
tmpArr = [0] * len(aArr)
ansArr = []
for i in range(len(aArr), 0, -1):
    tmp = aArr[i-1]
    if i == 0:
        s = tmpArr
    else:
        s = tmpArr[::i]
    su = sum(s)
    if su % 2 != tmp:
        tmpArr[i-1] = 1
        ansArr.append(i)
print(sum(tmpArr))
print(" ".join(map(str,ansArr)))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

d = defaultdict(int)

def trial_division(n):
    
    tmp = int(n ** 0.5) + 1
    for num in range(2, tmp):
        while n % num == 0:
            d[num] += 1
            n //= num
    if n > 1:
        d[n] += 1

    return

b = [0] * N
cnt = 0
for i in range(N, 0, -1):
    if d[i] % 2 == 1 and a[i-1] == 0:
        b[i-1] = 1
        cnt += 1
    elif d[i] % 2 == 0 and a[i-1] == 1:
        b[i-1] = 1
        cnt += 1
    trial_division(i)

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

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a_s = list(map(int, input().split(' ')))
    results = []
    for i, a in enumerate(a_s):
        if sum(a_s[i:]) % 2 != a:
            print(-1)
            quit()
        elif a == 1:
            results.append(str(i+1))
    print(len(results))
    if results:
        print(' '.join(results))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

box = [0]*n
for i in range(n, 0, -1):
    for j in range(n//i): box[i-1] -= box[i*(j+1)-1]
    box[i-1] += a[i-1]
    if box[i-1]<0: exec("print(-1);exit()")

print(box[0])
for i, m in enumerate(box):
    if m: print(i+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = list(map(int, input().split()))
sum_ = sum(arr)

if sum_ == 0:
	print(0)
else:
	output = []

	for i in range(1, n + 1):
		total = 0
		for j in range(i, n + 1, i):
			total += 1

		if (total - arr[i - 1]) % 2 == 0:
			output.append(i)

	if output == []:
		print(-1)
	else:
		for i in output:
			print(i, end=' ')

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [0] * n
if n % 2 == 0:
    mid = n//2 - 1
else:
    mid = (n//2)

for i in range(mid, n):
    b[i] = a[i]

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


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

Submission status: Wrong Answer

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

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

b = [0] * n
for i in reversed(range(1, n + 1)):
    s = 0
    for j in range(i + 1, n + 1, i):
        #if j % i == 0 and j != i:
        s += a[j - 1]

    if s % 2 == a[i - 1]:
        b[i - 1] = 0
    else:
        b[i - 1] = 1
#print(b)
e = sum(b)
print(e)

if e != 0:
    d = []
    for i in range(n):
        if b[i] == 1:
            d.append(i + 1)
    print(' '.join(map(str, d)))

Submission status: Wrong Answer

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

n = int(input())
a = list(map(int,input().split()))
b = []
for i in reversed(range(0, n)):
    ne = (i+1)*2
    if ne > n:
        if a[i] == 1:
            b.append(str(i+1))
    else:
        if a[i] != a[ne -1]:
            b.append(str(i+1))
print(len(b))
print(' '.join(b))

Submission status: Wrong Answer

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

end_flag = False
for i, a in enumerate(a_list):
  if a == 1:
    print(str(i+1))
    print(a)
    end_flag = True
    break
    
if not end_flag:
  print('0')

Submission status: Wrong Answer

Solution code:
import sys


def add_ball(idx):
    b_list[idx] = (b_list[idx]+1)%2
    if idx > 0:
        b_list[0] = (b_list[0]+1)%2
        idx += 1 # 0-origin to 1-origin
        for j in range(2, idx):
            if idx%j == 0:
                k = int(idx/j)
                if j == k:
                    b_list[j] = (b_list[j]+1)%2
                    break
                elif j < k:
                    b_list[j] = (b_list[j]+1)%2
                    b_list[k] = (b_list[k]+1)%2
                else:
                    break


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

    n = int(input())
    a_list = list(map(int, input().split()))
    b_list = [0] * n
    for i, a in enumerate(a_list[::-1]):
        if a != b_list[-i-1]:
            add_ball(n-i-1)
    ball_sum = sum(b_list)
    ball_list = [i+1 for i, b in enumerate(b_list) if b == 1]
    print(ball_sum)
    if ball_sum > 0:
        print(' '.join(map(str, ball_list)))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
l = [0 for i in range(N)]
ans = []
memo = 0
cnt = 0
for i in reversed(range(N)):
    j = 2
    while (i+1)*j <= N:
        memo += a[(i+1)*j-1]
        j += 1
    memo = memo%2
    if memo != a[i]:
        l[i] = 1
        cnt += 1
        ans.append(str(i))
ans.sort()
print(cnt)
print(" ".join(ans))

Submission status: Wrong Answer

Solution code:
import sys

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

b = [-1 for _ in range(n+1)]
k = 2

for i in reversed(range(1, n+1)):
    if i <= n / k:
        sum = 0
        for j in range(i+1,n+1):
            sum += b[j]
        if sum % 2 == a[i-1]:
            b[i] = 0
        else:
            b[i] = 1
        k += 1
    else:
        b[i] = a[i-1]

m = b.count(1)
print(m)
if m == 0:
    sys.exit()

resb = list(map(lambda y: y[1], filter(lambda x: x[1] > 0, zip(range(n+1), b))))
print(*resb)

Submission status: Wrong Answer

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

def solve(N: int, a: "List[int]"):
    dp = [0] * N
    for i in range(N, 0, -1):
        if i > N // 2:
            dp[i-1] = a[i-1]
        else:
            for j in range(2, N // i):
                dp[i-1] = dp[j * (i-1)]
            dp[i-1] += a[i-1]
            dp[i-1] %= 2
    print(sum(dp))
    s = []
    for i in range(N):
        if dp[i] == 1:
            s.append('%d' % (i + 1))
    if len(s) > 0:
        print(' '.join(s))
    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: Wrong Answer

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

b=[-1]*N
b[N-1]=a[N-1]
for i in range(N-1)[::-1]: #N=4なら 2,1,0
    sum_count = N // (i+1)
    if sum_count==1:
        b[i]=a[i]
    else:
        sum1=0
        for j in range(sum_count-1):
            sum1 = sum1 + b[(i+1)*(j+1)]
        sum1 = sum1 % 2
        b[i]=(a[i]+ sum1)%2

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())

a = list(map(int, input().split()))
b = [0] * N
flag = True
for k in range(N):
    i = N - k
    count = 0
    for m in range(i, N, i):
        count += b[m]
    t1 = count % 2
    t2 = (count + 1) % 2
    print(i, a[i - 1], count, b)
    if t1 == a[i - 1]:
        pass
    elif t2 == a[i - 1]:
        b[i - 1] = 1
    else:
        print(-1)
        flag = False
        break

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

Submission status: Wrong Answer

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

ball = [0]*(n+1)
for j in range(n//2+1, n+1):
    ball[j] = a[j-1]
for i in range(n//2, 0, -1):
    summ = 0
    for k in range(2, n+1):
        if i*k > n:
            break
        else:
            summ += a[i*k-1]
    if a[i-1] == (summ%2):
        ball[i] = 0
    else:
        ball[i] = 1

print(sum(ball))
if sum(ball) > 0:
    ans = []
    for l in range(1, n+1):
        if ball[l] == 1:
            ans.append(l)
    print(' '.join(map(str, ans)))

Submission status: Wrong Answer

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

B = [0] * (N)
BB = []
cnt_b = 0
for i in range(N)[::-1]:
    sum_b = 0
    idx = 1
    while True:
        if (i+1) * idx > N:
            B[i] = (A[i] + sum_b)%2
            if B[i] == 1:
                cnt_b += 1
                BB.append(i+1)
            break
        else:
            sum_b = B[(i+1)*idx-1]
        idx += 1
print(cnt_b)
str_b = ' '.join(map(str, BB))
if str_b != '0':
    print(str_b)

Submission status: Wrong Answer

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

    # divisors.sort()
    #return divisors

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

B=[0]*300000
C=[]
count=0
for i in reversed(range(N)):
    if B[i+1]%2!=A[i]:
        make_divisors(i+1)
        count +=1
        C.append(i+1)
print(count)
print(B)
if count!=0:
    for i in reversed(range(1,count)):
        print(str(C[i])+" ",end="")
    print(C[0], end="")

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

n = int(input())
seq = [int(x) for x in input().split(" ")]


def check_by_index(s, i):
    n = len(s)
    a = s[i]
    j = 1
    summation = 0
    while (i + 1) * j - 1 < n:
        summation += s[((i + 1) * j) - 1]
        j += 1
    residue = summation % 2
    return residue == a,


m = 0
for i in range(0, len(seq)):
    ok = check_by_index(seq, i)
    if not ok:
        print(-1)
        sys.exit(0)

m = seq.count(1)
print(m)
if m == 0:
    sys.exit(0)

indices = []
for i in range(0, len(seq)):
    if seq[i] == 1:
        indices.append(str(i+1))

print(" ".join(indices))

Submission status: Wrong Answer

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

end_flag = False
for i, a in enumerate(a_list):
  if a == 1:
    print(str(i+1))
    num = N // (i+1)
    b_list = [ str((b + 1) * (i+1)) for b in range(num)]
    print(' '.join(b_list))
    end_flag = True
    break
    
if not end_flag:
  print('0')

Submission status: Wrong Answer

Solution code:
import sys

import math

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

ball_arr = [0] * N

for i in range(math.ceil(N/2), N):
    ball_arr[i] = a[i]
    
# print(ball_arr)

for i in reversed(range(math.ceil(N/2))):
    # print(i+1)
    # print(sum(ball_arr[i-1::i+1]))
    # print(sum(ball_arr[i-1::i+1]) != a[i])
    mul_arr = ball_arr[i-1::i+1]
    if sum(mul_arr) % 2 != a[i]:
        # print((mull_arr.index(0)+1)*i)
        if 0 in mul_arr: 
            ball_arr[(mul_arr.index(0)+1)*i] = 1
        else:
            print(-1)
            sys.exit()
    # print(ball_arr)
    # print('---')
# print(ball_arr)

M = sum(ball_arr)
print(M)
for i, v in enumerate(ball_arr):
    if v == 1:
        print(i+1, end=' ')

Submission status: Wrong Answer

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)

    return divisors


N = int(input())
A = map(int, raw_input().split())
C = [0 for j in range(N)]
ANS = []

for j in range(N, 0, -1):
    m = A[j-1] % 2
    am = (A[j-1] + C[j-1]) % 2
    if m != am:
        A[j-1] += 1
        ANS.append(j)
    if 0 < A[j-1]:
        div = make_divisors(j)
        for k in div:
            if k != j:
                C[k-1] += A[j-1]

print(len(ANS))
str_ANS = [str(j) for j in ANS]
print(" ".join(str_ANS))

Submission status: Wrong Answer

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

for n in range(int(N / 2), 0, -1):
    if A[n-1] == sum(A[i-1] for i in range(2*n, N, n)):
        A[n-1] = 0
    else:
        A[n-1] = 1

ans = sum(A)
print(ans)
if ans > 0:
    print(*[i+1 for i, a in enumerate(A) if a == 1], sep=" ")

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

ans = [0 for _ in range(N // 2 + 1)] + A[N // 2:]

for i in range(N // 2, 1, -1):
    count = 0
    n = i
    j = 2
    while n * j <= N:
        count += ans[n * j]
        j += 1
    ans[i] = (count + A[i - 1]) % 2

sans = sum(ans)

ans[1] = (sans + A[0]) % 2

sans += ans[1]

print(sans)
p = ''
for i in range(1, N + 1):
    if ans[i] == 1:
        p += str(i) + ' '

print(p)

Submission status: Wrong Answer

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

M = A[0]
chk = [0]*N

A.reverse()
for i, a in enumerate(A):
    if a == 0:
        continue
    elif a == 1:
        chk[N-i-1] = 1
        continue
    else:
        sum_chk = sum(chk[N-i-1::N-i])
        if N/(N-i) < a:
            print(-1)
            exit()
        elif sum_chk == a-1:
            chk[N-i-1] = 1
            continue
        elif sum_chk == a:
            continue
        else:
            print(-1)
            exit()

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

Submission status: Wrong Answer

Solution code:
import sys

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)

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

if AList[0] == 0:
  print(0)
  exit()

lcmList=[]
for i in range(N):
  if AList[i] == 1:
    lcmList.append(i+1)
    
if len(lcmList)==0:
  print(0)
  exit()
    
lcmNum=lcmList[0]
for i in range(1,len(lcmList)):
  lcmNum=lcm(lcmNum,lcmList[i])
    
if lcmNum > N:
  print(0)
else:
  print(1)
  print(lcmNum)

Submission status: Wrong Answer

Solution code:
def div(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[:-1]

N = int(input())

A = [int(i) for i in input().split()]
B = [0] * N
mid = N // 2

for i in range(mid, N)[::-1]:
  B[i] = A[i]
  for k in div(i+1):
    B[k-1] += A[i]

for i in range(mid)[::-1]:
  B[i] = B[i] % 2
  if B[i] != A[i]:
    B[i] = 1
  else:
    B[i] = 0
  for k in div(i+1):
    B[k-1] += B[i]

S = ""    
for i in range(N):
  if B[i] == 1:
    S = S + str(i+1) + " "
if len(S) > 0:
  print(S[:-1])
else:
  print(0)

Submission status: Wrong Answer

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

result = []
for i in range(N):
    if a[i] == 1:
        result.append(i + 1)
M = len(result)
print(M)
for i in range(M):
    print(result[i], end = " ")

Submission status: Wrong Answer

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

if c%2 == 1:
    print('-1')
else:
    print(c)
    print(" ".join(repr(e) for e in ans))

Submission status: Wrong Answer

Solution code:
n = int(input())

a = []
aa = input().split() 

for i in range(n):
    a.append(int(aa[i]))

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

memo = int(n/2)+2
for i in range(n-1,-1,-1):
    if i >= memo:
        ans[i] = a[i]
    else:
        memo2 = 0
        s = i+1
        t = 2
        while (s*t-1)<=(n-1):
            if ans[s*t-1] == 1:
                memo2 += 1
            t += 1
        if a[i] != memo2%2:
                ans[i] = 1

v = 0
for i in range(n):
    if ans[i] == 1:
        v += 1

print(v)

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

Submission status: Wrong Answer

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


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

    # divisors.sort()
    return divisors


num = int(N // 2 + 1)
cnt = {}
for i in range(1, N + 1):
    cnt[i] = 0
A.reverse()
B = []

for i, a in enumerate(A):
    i = N - i
    if i > num:
        if a == 1:
            for p in make_divisors(i):
                cnt[p] = (cnt[p] + 1)
            B.append(i)
    else:
        if cnt[i] != a:
            for p in make_divisors(i):
                cnt[p] = (cnt[p] + 1)
            B.append(i)

print(len(B))
B = list(map(str, B))
print(' '.join(B))

Submission status: Wrong Answer

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

ans=[0]*n

i=n-1
j=1
f=0
while i!=-1:
    while True:
        try:
            b=i+(i+1)*j
            f+=ans[b]
            j+=1
        except:
            break
    f=f%2
    if (f-s[i])==0:
        ans[i]=0
    else:
        ans[i]=1
    j=1
    i-=1
sad=[]
print(ans.count(1))
i=0
while i!=len(s):
    if ans[i]==1:
        sad.append(i+1)
    i+=1


print(' '.join(map(str, sad)))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0]*N
n = N
for a in (reversed(A)):
    if n*2 > N:
        B[n-1] = a
        n -= 1
        continue
    total = 0
    for i in range(2,N+2):
        if n*i <= N:
            total += B[n*i-1]
        else:
            if a == total % 2:
                B[n-1] = 0
            else:
                B[n-1] = 1
    n -= 1

M = sum(B)
B = [str(b) for b in B]
print(M)
print(' '.join(B))

Submission status: Wrong Answer

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

sum=0
count=0
OK_Flag=True
OK_list=[]

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

if OK_Flag==True:
  print(count)
  if count!=0:
    print(' '.join(map(str, OK_list)))
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = []
for i in range(n):
    x = n-i
    y = 0
    for j in range(n):
        if x*(j+2) <= n:
            if a[x*(j+2)-1] == 1:
                y += 1
        else:
            break
    ymod = y%2
    if not ymod == a[x-1]:
        ans.append(x)
s = len(ans)
print(s)
if s > 0:
    print(" ".join([str(i) for i in ans]))

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

for i in reversed(range(N)):
    if A[i] == 1:
        put.append(i+1)
        # iを素因数分解して、約数に1をxorしていく
        if i != 0:
            A[0] ^= 1
        tmp = 2
        n = i+1
        while tmp*tmp <= n:
            if n % tmp == 0:
                A[tmp-1] ^= 1
            tmp += 1


if len(put) > 0:
    print(len(put))
    print(*put)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
n=int(input())
L=[0 for i in range(n+1)]
a=list(map(int,input().split()))
for i in range((n//2)+1,n+1):
  L[i]=a[i-1]
  if L[i]==1:
    for j in range(1,int(i**0.5)+1):
      if i%j==0:
        L[j]+=1
        if j*j!=i and j!=1:
          L[i//j]+=1
for i in range(n//2,0,-1):
  L[i]=(a[i-1]+L[i])%2
  if i!=1 and L[i]==1:
    for j in range(1,int(i**0.5)+1):
      if i%j==0:
        L[j]+=1
        if j*j!=i and j!=1:
          L[i//j]+=1
ct=0
for i in range(1,len(L)):
  if L[i]==1:ct+=1
print(ct)
for i in range(1,len(L)):
  if L[i]==1:print(i)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def primes(n):
    p = 2
    dd = defaultdict(list)
    while p <= n:
        if p in dd:
            for q in dd[p]:
                dd[p + q].append(q)
        else:
            yield p
            dd[p * p].append(p)
        p += 1

if __name__ == '__main__':
    n = int(input())
    a = [int(s) for s in input().split()]
    b = [0] * n
    ps = list(primes(n))
    for i in range(n, 0, -1):
        b[i - 1] = a[i - 1]
        for v in ps:
            j = v * i
            if j > n:
                break
            b[i - 1] ^= a[j - 1]
    m = b.count(1)
    print(m)
    if m:
        print(*(i + 1 for i, x in enumerate(b) if x))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

#n ... 番目の箱　b[n-1]　のボールの数
blist = []
for j in range(n-1,-1,-1):
    if a[j] == 1:
        k=j+1
        count= 0
        while k<=n:
            count = count + b[k-1]
            k = k+j+1
        if count%2 == 0:
            b[j] = 1
            blist.append(j+1)
sb = sum(b)
print(sb)
if sb > 0:
    strb = " ".join(map(str,blist))
    print(strb)