101343: [AtCoder]ABC134 D - Preparing Boxes

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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.

Input

题意翻译

给你一个序列 a ,构造一个数列 b ,(两个数列中的数均为0或1)满足以下条件: 对于位置 $ i $ , 将所有是 $ i $ 的倍数的下标的值相加,其和 $ mod $ $ 2 $ 的结果为 $ ai $

加入题单

上一题 下一题 算法标签: