A12148 | Space Isaac
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
Everybody seems to think that the Martians are green, but it turns out they are metallic pink and fat. Ajs has two bags of distinct nonnegative integers. The bags are disjoint, and the union of the sets of numbers in the bags is $\{0,1,…,M-1\}$ , for some positive integer $M$ . Ajs draws a number from the first bag and a number from the second bag, and then sums them modulo $M$ .
What are the residues modulo $M$ that Ajs cannot obtain with this action?
What are the residues modulo $M$ that Ajs cannot obtain with this action?
输入格式
The first line contains two positive integer $N$ ( $1 \leq N \leq 200\,000$ ) and $M$ ( $N+1 \leq M \leq 10^{9}$ ), denoting the number of the elements in the first bag and the modulus, respectively.
The second line contains $N$ nonnegative integers $a_1,a_2,\ldots,a_N$ ( $0 \leq a_1<a_2< \ldots< a_N<M$ ), the contents of the first bag.
The second line contains $N$ nonnegative integers $a_1,a_2,\ldots,a_N$ ( $0 \leq a_1<a_2< \ldots< a_N<M$ ), the contents of the first bag.
输出格式
In the first line, output the cardinality $K$ of the set of residues modulo $M$ which Ajs cannot obtain.
In the second line of the output, print $K$ space-separated integers greater or equal than zero and less than $M$ , which represent the residues Ajs cannot obtain. The outputs should be sorted in increasing order of magnitude. If $K$ =0, do not output the second line.
In the second line of the output, print $K$ space-separated integers greater or equal than zero and less than $M$ , which represent the residues Ajs cannot obtain. The outputs should be sorted in increasing order of magnitude. If $K$ =0, do not output the second line.
输入输出样例
输入 #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
In the first sample, the first bag and the second bag contain $\{3,4\}$ and $\{0,1,2\}$ , respectively. Ajs can obtain every residue modulo $5$ except the residue $2$ : $ 4+1 \equiv 0, \, 4+2 \equiv 1, \, 3+0 \equiv 3, \, 3+1 \equiv 4 $ modulo $5$ . One can check that there is no choice of elements from the first and the second bag which sum to $2$ modulo $5$ .
In the second sample, the contents of the first bag are $\{5,25,125,625\}$ , while the second bag contains all other nonnegative integers with at most $9$ decimal digits. Every residue modulo $1\,000\,000\,000$ can be obtained as a sum of an element in the first bag and an element in the second bag.
In the second sample, the contents of the first bag are $\{5,25,125,625\}$ , while the second bag contains all other nonnegative integers with at most $9$ decimal digits. Every residue modulo $1\,000\,000\,000$ can be obtained as a sum of an element in the first bag and an element in the second bag.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted