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 unittest


class TestD(unittest.TestCase):
    def test_1(self):
        a = [1, 0, 0]
        b = think(a)
        self.assertEqual(is_valid(a, b), True)

    def test_2(self):
        a = [0, 0, 0, 0, 0]
        b = think(a)
        self.assertEqual(is_valid(a, b), True)

    def test_3(self):
        a = [1, 1, 1, 1, 1, 1, 1]
        b = think(a)
        self.assertEqual(is_valid(a, b), True)

    def test_4(self):
        a = [1, 1, 1, 0, 1, 1, 0, 0]
        b = think(a)
        self.assertEqual(is_valid(a, b), True)


def solve():
    a = read()
    b = think(a)
    write(b)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_float(n):
    return list(map(lambda x: float(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    b = [0 for x in range(len(a))]
    for i in range(len(a), 0, -1):
        # print(i)
        count = 0
        for j in range(i, len(a) + 1, i):
            # print(j, ' ', end='')
            count += b[j - 1]
        # print('', b, ',', count, ',', a[i - 1])
        if a[i - 1] % 2 == count % 2:
            b[i - 1] = 0
        else:
            b[i - 1] = 1
    result = []
    for i in range(len(b)):
        if b[i] == 1:
            result.append(i + 1)
    return result


def write(b):
    print(len(b))
    print(' '.join(list(map(str, b))))


def is_valid(a, b):
    buf = [0 for x in range(len(a))]
    for i in b:
        buf[i - 1] = 1
    for i in range(len(a)):
        mod = i + 1
        count = 0
        for j in range(len(a)):
            to_be_divided = j + 1
            if to_be_divided % mod == 0:
                if buf[j]:
                    count += 1
        if count % 2 == a[i]:
            continue
        return False
    return True


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

ans_l = [0 for i in range(n)]
for i in reversed(range(n+1)):
    if i == 0:
        break
    now = 0
    for j in range(2,n+1):
        if j * i <= n:
            now += ans_l[j*i-1]
        else:
            break
    if now%2 == al[i-1]:
        ans_l[i-1] = 0
    else:
        ans_l[i-1] = 1
        
print(sum(ans_l))
for idx,i in enumerate(ans_l):
    if i == 1:
        print(idx+1)

Submission status: Accepted

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

#print(ai)
dai={}
dbi={}
for i in range(1, n+1):
    dai.setdefault(i, ai[i-1])
    dbi.setdefault(i, 0)

#print(dai)
#print(dbi)

anssum=0
ans=[]
for i in range(1, n+1)[::-1]:
    #print(i)
    tmp=0
    for j in range(2, n+1):
        check=i*j
        if check <= n:
            tmp = tmp + dbi[check]
        else:
            break
    tmp = tmp%2
    #print(str(tmp) + ", " + str(dai[i]))
    if tmp != dai[i]:
        dbi[i]=1
        anssum=anssum+1
        ans.append(i)

#print(dbi)
print(anssum)
if anssum != 0:
    print(" ".join(map(str, reversed(ans))))

Submission status: Accepted

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

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

print(sum(t))
print(*[i + 1 for i in range(N) if t[i] == 1])

Submission status: Accepted

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

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

print(sum(t))
print(*[i for i in range(1, N + 1) if t[i] == 1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=['$']+list(map(int,input().split())) # 1-index
    ans=[0]*(n+1)
    for i in range(n,0,-1): # iを確定させたい
        parity=A[i]
        for j in range(2,n//i+1): # iの倍数のうち、i以外のものを全てみる
            parity+=ans[i*j]
        if(parity%2): ans[i]=1
    s=sum(1 for i in range(1,n+1) if ans[i])
    print(s)
    if(s):
        print(*(i for i in range(1,n+1) if ans[i]))
resolve()

Submission status: Accepted

Solution code:
n=int(input())
a=[0]+list(map(int,input().split()))
b=[0]*(n+1)
for i in reversed(range(1,n+1)):
    if sum(b[i::i])%2!=a[i]:
        b[i]=1
print(sum(b))
for i,j in enumerate(b):
    if j==1:
        print(i,end=' ')

Submission status: Accepted

Solution code:
n = int(input())
a = input()
r = [None] * (n + 1)
for i in range(n, 0, -1):
    r[i] = (ord(a[2 * i - 2]) + sum(r[i * 2::i])) % 2
print(r.count(1))
print(*(i for i, x in enumerate(r) if x))

Submission status: Accepted

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

MOD = 2  # type: int


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

    answer2 = []
    for index,ans in enumerate(answer):
        if ans == 1:
            answer2.append(index)

    print(*answer2)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(n, 0, -1):
    tmp = 0
    for j in range( 2*i, n+1, i ):
        tmp += b[j]
    if tmp%2 != a[i]:
        res += 1
        b[i] = 1
for i in range(1, n+1):
    if b[i] == 1:
        ary.append(i)
print(res)
if res != 0:
    print(*ary)

Submission status: Accepted

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

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


for i in range(1, n+1):
    if i == n:
        if a[0] == 1 and sum(b) % 2 == 0:
            b[0] = 1
            count += 1
        elif a[0] == 0 and sum(b) % 2 == 1:
            b[0] = 1
            count += 1
    elif a[n-i] == 1 and sum(b[n-i::n-i+1]) % 2 == 0:
        b[n-i] = 1
        count += 1
    elif a[n-i] == 0 and sum(b[n-i::n-i+1]) % 2 == 1:
        b[n-i] = 1
        count += 1


if count == 0:
    print(-1)
else:
    print(count)
    for i in range(len(b)):
        if b[i] == 1:
            print(i+1, end=' ')

Submission status: Accepted

Solution code:
n = int(input())
a = [0]
a.extend(list(map(int, input().split())))
ans = [0 for _ in range(n+1)]
for i in range(n//2 + 1, n + 1):
    ans[i] = a[i]
for j in range(2, n+1):
    for i in range(n//(j+1) + 1, n//j + 1):
        if sum([ans[k*i] for k in range(2, j+1)]) % 2 != a[i]:
            ans[i] = 1
answer = [i for i, x in enumerate(ans) if x == 1]
l = len(answer)
print(l)
for i in range(l):
    if i <= l-2:
        print(answer[i], end=" ")
    else:
        print(answer[i])

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = []

N = I()
A = LI()
dp = [0]*N

for i in range(N-1,-1,-1):
    judge = int(0)
    if A[i]==1:
        judge +=1
    k = int(i + 1)
    while k < N:
        k += (i+1)
        if k<N+1 and dp[k - 1] == 1:
            judge += 1
#    if judge%2 != A[i]:
#        print("-1")
#        print(judge,i)
#        exit()
#    else:
    dp[i] = judge%2

#print(dp)
print(sum(dp))
for i in range(N):
    if dp[i]==1:
        ans.append(i+1)

print(" ".join(map(str,ans)))

Submission status: Accepted

Solution code:
def main():
    import sys
    n = int(input())
    a = list(map(int, input().split()))

    box = [0 for _ in range(n+1)]
    result = []
    for i in range(n, 0, -1):
        counter = 0
        for j in range(1, (n//i)+1):
            counter += box[j*i]
        if counter % 2 != a[i-1]:
            box[i] = 1
            result.append(i)
    """
    for i in range(1, n+1):
        counter = 0
        for j in range(1, (n//i)+1):
            counter += box[j*i]
        if counter%2 != a[i-1]:
            print(-1)
            sys.exit()
    """
    print(len(result))
    if len(result) != 0:
        print(*result[::-1])  
if __name__ == '__main__':
    main()

Submission status: Accepted

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

box = [0 for _ in range(n+1)]
result = []
for i in range(n, 0, -1):
    counter = 0
    for j in range(1, (n//i)+1):
        counter += box[j*i]
    if counter % 2 != a[i-1]:
        box[i] = 1
        result.append(i)
for i in range(1, n+1):
    counter = 0
    for j in range(1, (n//i)+1):
        counter += box[j*i]
    if counter%2 != a[i-1]:
        print(1)
        sys.exit()

print(len(result))
if len(result) != 0:
    print(*result[::-1])

Submission status: Accepted

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

box = [0 for _ in range(n+1)]
result = []
for i in range(n, 0, -1):
    counter = 0
    for j in range(1, (n//i)+1):
        counter += box[j*i]
    if counter % 2 != a[i-1]:
        box[i] = 1
        result.append(i)
for i in range(1, n+1):
    counter = 0
    for j in range(1, (n//i)+1):
        counter += box[j*i]
    if counter%2 != a[i-1]:
        print(-1)
        sys.exit()

print(len(result))
if len(result) != 0:
    print(*result[::-1])

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    ls = [0] * n
    ans = []
    for i in range(n-1, -1, -1):
        t = 0
        for j in range(i, n, (i+1)):
            t += ls[j]
        if t % 2 != a[i]:
            ls[i] = 1
            ans.append(i + 1)
    print(len(ans))
    if len(ans) != 0:
        print(*ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0]*N
answer = []
for i in range(N, 0, -1):
  if A[i-1] == 1:
    count = 1
    number = 0
    while count*i <= N:
      number += B[count*i-1]
      count+=1
    if number%2 == 0:
      B[i-1] = 1
      answer.append(i)
  else:
    count = 1
    number = 0
    while count*i <= N:
      number +=B[count*i-1]
      count+=1
    if number%2==1:
      B[i-1] = 1
      answer.append(i)
print(B.count(1))
print(*answer)

Submission status: Accepted

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

ball = [0]*N

for i in reversed(range(N)):
    Sum = 0
    x = 2
    while((i+1)*x <= N):
        Sum += ball[(i+1)*x-1]
        x += 1

    ball[i] = (Sum + a[i]) % 2

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

Submission status: Accepted

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

ans = [0 for i in range(n)]
for num in range(n,0,-1):
  cnt = 0
  for nu in range(num-1,n,num):
    cnt += ans[nu]
  if lis[num-1] != cnt % 2:
    ans[num-1] = 1
cnt1 = 0
for num in range(n):
  if ans[num] == 1:
    cnt1 += 1
print(cnt1)
for i in range(n):
  if ans[i] == 1:
    print(i+1,end = " ")

Submission status: Accepted

Solution code:
N=int(input())
AL=list(map(int, input().split()))
L=[]
for i in range(N-1,-1,-1):
    s=AL[i]
    for j in range((i+1)*2-1,N,i+1):
        s^=AL[j]
    AL[i]=s
    if AL[i]==1:
        L.append(i+1)
print(len(L))
if L:
    print(*L)

Submission status: Accepted

Solution code:
N=int(input())
AL=list(map(int, input().split()))
L=[]
for i in range(N-1,0,-1):
    s=AL[i]
    for j in range((i+1)*2-1,N,i+1):
        s^=AL[j]
    AL[i]=s
    if AL[i]==1:
        L.append(i+1)
AL[0]^=(len(L)%2)
if AL[0]==1:
    L.append(1)
print(len(L))
if L:
    print(*L)

Submission status: Accepted

Solution code:
n = int(input())

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

memo = [0]*n
ans_list = []
memo_count = 0
for i in range(n-1,-1,-1):
	if (i+1)*2 <= n:
		memo_count = 0
		for j in range(2,n//(i+1)+1):
			memo_count += memo[(i+1)*j-1]
		if memo_count%2 != list1[i]:
			memo[i] = 1
			ans_list.append(i+1)

	else:
		if list1[i] == 1:
			memo[i] = 1
			ans_list.append(i+1)

ans_list.sort()

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
A=list(map(int,input().split()))

count=0
ans=[]
hako=[0]*N
for i in range(N)[::-1]:
    all=0
    for j in range(i,N)[::i+1]:
        if i==j:
            continue
        all^=hako[j]
    if all==1:
        if A[i]==1:
            continue
        else:
            hako[i]=1
            count+=1
            ans.append(i+1)
    else:
        if A[i]==1:
            hako[i]=1
            count+=1
            ans.append(i+1)
        else:
            continue
ans.sort()
print(count)
print(*ans)
#print(hako)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
flag = [-1] * (N+1)
answer_list = []
for i in range(N):
    counter = 0
    i_num = N - i
    for j in range(i_num, N+1, i_num):
        if j == i_num:
            continue
        else:
            if flag[j] == 1:
                counter += 1
    if counter % 2 == A[i_num - 1]:
        flag[i_num] = 0
    else:
        flag[i_num] = 1
        answer_list.append(i_num)
print(len(answer_list))
if answer_list:
    print(" ".join(map(str, answer_list)))

Submission status: Accepted

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

N = int(input().split()[0])
a_list = list(map(int, input().split()))

# 最初が0から始まる場合
a_list = [0] + a_list
b_list = [0] * (N + 1)
# インデックスがずれるのがややこしいので、
# b_list[0]は欠番として1始まりで考えていく

for i in range(N):
    # 大きい方から決めていく
    idx = N - i
    total = sum(b_list[idx : N + 1 : idx])

    if total % 2 != a_list[idx]:
        b_list[idx] = 1

idx_list = [str(i) for i, b in enumerate(b_list) if b == 1]
ans = sum(b_list[1:])
print(ans)
if ans != 0:
    print(" ".join(idx_list))

Submission status: Accepted

Solution code:
import bisect

def solve():
    N = int(input())
    a = list(map(int, input().split()))
    b = []
    c = [0] * (N)

    M = 0

    for i in range(N - 1, -1, -1):
        if i >= N // 2:
            if a[i] == 1:
                b.append(i+1)
                c[i] = 1
                M += 1
            else:
                c[i] = 0
        else:
            num = i
            cnt = 0
            j = 2
            while (i+1) * j <= N:
                num = (i+1) * j
                cnt += c[num-1]
                j += 1
            if cnt % 2 == 0:
                if a[i] == 0:
                    c[i] = 0
                else:
                    b.append(i+1)
                    c[i] = 1
                    M += 1
            else:
                if a[i] == 0:
                    b.append(i+1)
                    c[i] = 1
                    M += 1
                else:
                    c[i] = 0
    
    print(M)
    if M != 0:
        print(*b)
    
    


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math

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

for i in range(n-1):
  ptr = n - 1 - i
  if a[ptr] % 2 == 1:
    a[0] += 1
    for j in range(2, int(math.sqrt(ptr+1))+1):
      if (ptr + 1) % j == 0:
        a[j-1] += 1
        if (ptr + 1) // j != j:
          a[(ptr + 1) // j - 1] += 1
      
cnt = 0
que = []
for  i in range(n):
  if a[i] % 2 == 1:
    cnt += 1
    que.append(i+1)

print(cnt)
if cnt > 0:
  print(' '.join(map(str, que)))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
'''
1 ~ N の倍数の箱を見ていくがN ~ 1の順で決めていく
'''
ans = [-1 for i in range(N)]
opt = []
for i in range(N,0,-1):
    p = N // i
    if p >= 2 :
        m = 0
        for x in range(2,p+1,1):
            m += ans[x*i-1]
        m = m % 2
        if m == A[i-1]:
            ans[i-1] = 0
        else :
            ans[i-1] = 1
            opt.append(i)
    else :
        if A[i-1] == 0 :
            ans[i-1] = 0
        else:
            ans[i-1] = 1
            opt.append(i)
print(sum(ans))
print(*opt)

Submission status: Accepted

Solution code:
N = int(input())
*A, = map(int, input().split())
B = [0 for _ in range(N)]
ans = []
for i in reversed(range(1, N+1)):
    temp = 0
    for j in range(2*i, N + 1, i):
        temp ^= B[j-1]
    if A[i-1] != temp: B[i-1] = 1; ans.append(i)
print(len(ans))
print(*ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# D - Preparing Boxes

# 先頭にダミーを加える

N = int(input())
a = [-1] + list(map(int, input().split()))

box = [-1] + [0]*N

for idx in reversed(range(1,N+1)):
    if sum([box[i] for i in range(idx, N+1, idx)]) % 2 == a[idx]:
        box[idx] = 0
    else:
        box[idx] = 1

print(sum(box[1:]))
for idx in range(N+1):
    if box[idx] == 1:
        print(idx)

Submission status: Accepted

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

b=[0]*(N+1)
M=0

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

    for j in range(i+i,N+1,i):
        if b[j] == 1:
            cnt += 1

    if a[i-1]==1 and cnt%2==0:
        b[i]=1
        M+=1
    elif a[i-1]==0 and cnt%2==1:
        b[i]=1
        M+=1
        

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

Submission status: Accepted

Solution code:
# iの倍数に入ったボールの和を2で割った余りa
n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(n)]
c = []
# impossible = False
# bを後ろから順に決定
for i in reversed(range(n)):
    sum_i = sum(b[i::i+1])
    if not sum_i % 2 == a[i]:
        b[i] = 1
        c.append(i+1)

print(sum(b))
if c:
    print(' '.join(map(str, c)))

Submission status: Accepted

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

for i in range(n):
    if sum(b[n-i-1:n:n-i]) % 2 != a[n-i-1]:
        b[n-i-1] += 1
        c.append(n-i)
print(len(c))
print(' '.join(map(str, c[::-1])))

Submission status: Accepted

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

b = [0] * N
M = 0
ans = []
for i in range(N, 0, -1):
    count = a[i-1]
    x = 2
    while x * i <= N:
        count += b[x*i-1]
        x += 1
    if count % 2 == 1:
        b[i-1] = 1
        M += 1
        ans.append(i)


print(M)
print(*ans)

Submission status: Accepted

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

# 分かりやすくするために一番目はb[1]としたい
b = [0] * (N + 1)
for i in reversed(range(1, N + 1)):
    if sum(b[i::i]) % 2 != a[i]:
        b[i] = 1

if a.count(1) == -1:
    print(0)
else:
    print(b.count(1))
    print(' '.join(map(str, [i for i, x in enumerate(b) if x == 1])))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = [0] + list(map(int,read().split()))

for n in range(N//2,0,-1):
    A[n] = sum(A[n::n])&1

I = [i for i,x in enumerate(A) if x]

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from functools import reduce
from operator import xor

N = int(readline())
A = [0] + list(map(int,read().split()))

for n in range(N//2,0,-1):
    A[n] = reduce(xor,A[n::n],0)

I = [i for i,x in enumerate(A) if x]

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from functools import reduce
from operator import xor

N = int(readline())
A = [0] + list(map(int,read().split()))

B = [0] * (N+1)
for n in range(N,0,-1):
    s = reduce(xor,B[n+n::n],0)
    B[n] = s^A[n]

I = [i for i,x in enumerate(B) if x]

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

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
b=[0]*N
for i in reversed(range(N)):
  k= N // (i+1)
  tmp=0
  for j in range(1,k):
    tmp+=b[(i+1)*(j+1)-1]
  b[i]=abs((tmp%2)-a[i])
M=sum(b)
ans=[]
for i in range(N):
  if b[i]==1:
    ans.append(i+1)
print(M)
print(" ".join(map(str,ans)))

Submission status: Accepted

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


ans = [0 for _ in range(N + 1)]
out = []
for idx in range(N, 0, -1):
	count = 0
	rep = 1
	while(idx * rep <= N):
		count += ans[idx * rep]
		rep += 1
		
	if A[idx] != count % 2:
		ans[idx] = 1
		out.append(idx)

print(len(out))
if(len(out)>0):
	print(" ".join(map(str, out)))

Submission status: Accepted

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


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

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
arr = list(map(int, input().split()))
puts = []
dd = defaultdict(int)

def make_divisors(n):
    divisors = []
    # Nの最大の約数は√N
    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

for i in range(1,N+1)[::-1]:
    if N//2 < i and arr[i-1] == 1:
        puts.append(i)
        ds = make_divisors(i)
        for j in ds:
            dd[j] += 1
    else:
        # c = len([p for p in puts if p % i == 0])
        c = dd[i]
        if (c % 2 == 0 and arr[i-1] == 1) or (c % 2 == 1 and arr[i-1] == 0):
            puts.append(i)
            ds = make_divisors(i)
            for j in ds:
                dd[j] += 1

print(len(puts))
if len(puts):
    print(" ".join(map(str, sorted(puts, reverse=True))))

Submission status: Accepted

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

    B = [0] * (N+1)

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

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

    print(cnt)
    print(*ans)

main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int,input().split()))
    res = [0 for i in range(n)]
    lres = []
    for i in range(n,0,-1):
        flag = 0
        t = i*2
        while t <= n:
            flag = flag ^ res[t-1]
            t = t+i
        if a[i-1] != flag:
            res[i-1] = 1
            lres.append(str(i))

    print(len(lres))
    if len(lres) != 0:
        print(" ".join(lres))

main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int,input().split()))
    res = [0 for i in range(n)]
    lres = []
    for i in range(n,0,-1):
        l = []
        flag = 0
        t = i*2
        while t <= n:
            flag = flag ^ res[t-1]
            t = t+i
        if a[i-1] != flag:
            res[i-1] = 1
            lres.append(str(i))

    print(len(lres))
    if len(lres) != 0:
        print(" ".join(lres))

main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
res = [0 for i in range(n)]
lres = []
for i in range(n,0,-1):
    l = []
    flag = 0
    t = i*2
    while t <= n:
        flag = flag ^ res[t-1]
        t = t+i
    if a[i-1] != flag:
        res[i-1] = 1
        lres.append(str(i))

print(len(lres))
if len(lres) != 0:
    print(" ".join(lres))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
res = [0 for i in range(n)]
for i in range(n,n//2,-1):
    res[i-1] = a[i-1]

for i in range(n//2,0,-1):
    l = []
    flag = 0
    t = i*2
    while t <= n:
        flag = flag ^ res[t-1]
        t = t+i
    if a[i-1] != flag:
        res[i-1] = 1

if res == [0 for i in range(n)]:
    print(0)
else:
    lres = []
    for i in range(n):
        if res[i] == 1:
            lres.append(str(i+1))
    print(len(lres))
    print(" ".join(lres))

Submission status: Accepted

Solution code:
N = int(raw_input())
A = list(map(int,raw_input().split()))
ans = [0]*N
for i in reversed(range(0, N)):
  ball = 0
  for j in range(i,N,i+1):
    ball = ball + ans[j]
  if (ball+A[i])%2!=0 :
    ans[i] = 1
print sum(ans)
if sum(ans) != 0:
  for i in range(0,len(ans)):
    if ans[i] != 0:
      print i+1,

Submission status: Accepted

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

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

for i in reversed(range(N)):
    j = i + 1
    tmp = 0
    while j <= N:
        tmp += b[j - 1]
        j += i + 1
    if (tmp + a[i]) % 2 == 1:
        b[i] = 1

M = sum(b)
print(M)
if M != 0:
    for i in range(N):
        if b[i] == 1:
            print(i + 1, end=' ')
    print('\n')

Submission status: Accepted

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

c = [-1] + [0] * n

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

for i in range(n // 2, 0, -1):
  sum = 0
  j = i + i
  while (j <= n):
    sum += c[j]
    j += i
  c[i] = (a[i] - sum) % 2

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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

# N = 6
# a =  [0, 0, 0, 1, 0, 1]
# ans: [1,    3, 4,    6]

# N = 6
# a =  [1, 1, 0, 1, 0, 1]
# ans: [1, 2, 3, 4,    6]

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


for i in range(N - 1, 0 , -1):
    # i は 5 から 1 までイテレートする
    # print('i', i)
    # print('a', a[::i][1:])
    # print('b', b[i::i+1])
    # print("")
    # あれ... a イテレートする必要なくない...??
    if (a[i] + sum(b[i::i+1])) % 2 == 0:
        b[i] = 0
    else:
        b[i] = 1

if a[0] == 0:
    b[0] = (sum(b[1:])) % 2
else:
    # print('kotti', sum(b[1:]))
    b[0] = (sum(b[1:]) + 1) % 2

# print('a', a)
# print('b', b)

s = sum(b)
print(s)
if s != 0:
    # print(*b[:last_index(b, 1) + 1])
    print(*[x + 1 for x in range(N) if 0 < b[x]])

Submission status: Accepted

Solution code:
N = int(input())
mod_arr = list(map(int,input().split()))
arr = [0]*N
in_arr = []
# iが大きい方から決めていく
for i in range(N,0,-1):
  if i > N//2:
    if mod_arr[i-1] == 0:
      continue
    else:
      arr[i-1] = 1
      in_arr.append(str(i))
      
  else:
    S = 0
    for j in range(2*i,N+1,i):
      S += arr[j-1]
    if S%2 == mod_arr[i-1]:
      arr[i-1] = 0
    else:
      arr[i-1] = 1
      in_arr.append(str(i))

print(len(in_arr))
print(' '.join(in_arr))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    lst_a = list(map(int, input().split()))
    ans = set()

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#import numpy as np

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

m = 0
ans = [0]*(n+1)
#ans = np.zeros(n+1).astype(int)


i=1
for i in range(n,0,-1):
    sum_num = 0
    for j in range(i,n+1,i):
        sum_num += ans[j]

    if((sum_num & 1) != a_s[i-1]):
        m += 1
        ans[i] = 1

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

print(m)
print(' '.join(map(str,ans2)))

Submission status: Accepted

Solution code:
#134d
import math
 
#input
#3
#1 0 0
#output
#1
#1
 
N = int(input()) #1≤N≤2×10^5
 
#Nの後半は入力と一致するので直接代入   
ans = list(map(int, input().split()))
 
#N 個の空の箱が横一列に並んでいます。 左から i  (1≤i≤N) 番目の箱には整数 iが書かれています。
#それぞれの箱に対してボールを 1個入れるか何も入れないかを選ぶことができます。
#ここで、以下の条件を満たすようなボールの入れ方を、いいボールの入れ方と定めます。
 
# 1以上 N 以下の任意の整数 i について、i の倍数が書かれた箱に入っているボールの個数の和を 2 で割った余りが aiである。
 
#いいボールの入れ方は存在するでしょうか。存在するならば 1つ求めてください。
 
if N%2==0:
    first = int(N/2)-1
else:
    first = int((N-1)/2)-1

#前半部分を処理
for i in range(first,-1,-1): # Max:10^5ループ
    #print(i,"→",i+1,":",ans[i])
    
    multiple_list = [(i+1)*j for j in range(1,1+N//(i+1))]
    #print(N,",",N//(i+1))
    #print(i+1,"の倍数:",multiple_list)
    #content = [ans[j-1] for j in multiple_list]
    #print("中身:",content)
    total = sum([ans[j-1] for j in multiple_list])
    
    if ans[i]==1 and total%2==0:
        ans[i] = 0
    elif ans[i]==0 and total%2==1:
        ans[i] = 1
        
#print(' '.join(map(str,ans)))
print(sum(ans))
print(' '.join(map(str,[j+1 for j in range(0,N) if ans[j]==1])))