← 返回题目列表

Codeforces · 1045/B

B. 太空艾萨克

中文机器翻译题面 查看原题

每个人似乎都认为火星人是绿色的,但事实证明他们是金属粉红色且肥胖。 Ajs 有两袋不同的非负整数。这些袋子是不相交的,对于某个正整数 $$$M$$$,袋子中数字集的并集是 $$$\{0,1,…,M-1\}$$$。 Ajs 从第一个袋子中抽取一个数字,从第二个袋子中抽取一个数字,然后对它们进行模 $$$M$$$ 求和。

Ajs 通过此操作无法获得模 $$$M$$$ 的余数是多少?

输入

第一行包含两个正整数 $$$N$$$ ($$$1 \leq N \leq 200\,000$$$) 和 $$$M$$$ ($$$N+1 \leq M \leq 10^{9}$$$),分别表示第一个包中元素的个数和模数。

第二行包含$$$N$$$非负整数$$$a_1,a_2,\ldots,a_N$$$ ($$$0 \leq a_1<a_2< \ldots< a_N<M$$$),即第一个包的内容。

输出

第一行输出Ajs无法获得的余数集模$$$M$$$的基数$$$K$$$。

在输出的第二行中,打印$$$K$$$空格分隔的大于等于零且小于$$$M$$$的整数,它们代表Ajs无法获得的余数。输出应按数量级递增的顺序排序。如果$$$K$$$=0,则不输出第二行。

示例

输入 #1

2 5
3 4

输出 #1

1
2

输入 #2

4 1000000000
5 25 125 625

输出 #2

0

输入 #3

2 4
1 3

输出 #3

2
0 2

注意

在第一个示例中,第一个包和第二个包分别包含 $$$\{3,4\}$$$ 和 $$$\{0,1,2\}$$$。 ajs 可以获得除余数 $$$2$$$ 以外的所有余数模 $$$5$$$: $$$ 4+1 \equiv 0, \, 4+2 \equiv 1, \, 3+0 \equiv 3, \, 3+1 \equiv 4 $$$ modulo $$$5$$$。人们可以检查是否没有从第一个和第二个包中选择元素,其总和为 $$$2$$$ 模 $$$5$$$。

在第二个示例中,第一个包的内容为 $$$\{5,25,125,625\}$$$,而第二个包包含所有其他非负整数,最多包含 $$$9$$$ 十进制数字。每个余数模 $$$1\,000\,000\,000$$$ 都可以作为第一个包中的元素与第二个包中的元素之和获得。