#ABC134D. Preparing Boxes
Preparing Boxes
题目描述
There are empty boxes arranged in a row from left to right. The integer is written on the -th box from the left .
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 between and (inclusive), the total number of balls contained in the boxes with multiples of written on them is congruent to mod .
Does there exist a good set of choices? If the answer is yes, find one good set of choices.
有 个空盒子,从左到右排成一行。整数 写在左起 的第 个盒子上。
对于每一个盒子,斯努克都可以选择放一个球或者什么都不放。
当满足以下条件时,我们说一组放球或不放球的选择是好的:
- 对于介于 和 (含)之间的每一个整数 ,写有 倍数的盒子中包含的球的总数与 同余,模为 。
是否存在一组好的选择?如果答案是肯定的,请找出一组好的选择。
输入格式
输入内容按以下格式标准输入:
输出格式
如果不存在一组好的选择,则打印 -1
。
如果存在一组好的选择,则按以下格式打印一组这样的选择:
$M$
$b_1$ $b_2$ $...$ $b_M$
其中 表示将包含一个小球的盒子数量, 是写在这些盒子上的整数,顺序不限。
样例 #1
样例输入 #1
3
1 0 0
样例输出 #1
1
1
样例 #2
样例输入 #2
5
0 0 0 0 0
样例输出 #2
0
说明
数据规模与约定
- 所有输入值均为整数。
- 是 或 。
样例 解释
考虑只在写有 的盒子里放一个球。
- 有三个盒子上写着 的倍数: 、 和 。这些盒子中包含的球的总数是 。
- 只有一个盒子上写着 的倍数:写着 的盒子。这些盒子中包含的球的总数是 。
- 只有一个盒子上写有 的倍数:写有 的盒子。这些盒子中包含的球的总数是 。
因此,条件满足,所以这组选择是好的。
样例 解释
在方框中什么都不放也是一组不错的选择。