English · Original
Chinese · Translation
Formal · Original
Astronaut Natasha arrived on Mars. She knows that the Martians are very poor aliens. To ensure a better life for the Mars citizens, their emperor decided to take tax from every tourist who visited the planet. Natasha is the inhabitant of Earth, therefore she had to pay the tax to enter the territory of Mars.
There are $n$ banknote denominations on Mars: the value of $i$\-th banknote is $a_i$. Natasha has an infinite number of banknotes of each denomination.
Martians have $k$ fingers on their hands, so they use a number system with base $k$. In addition, the Martians consider the digit $d$ (in the number system with base $k$) divine. Thus, if the last digit in Natasha's tax amount written in the number system with the base $k$ is $d$, the Martians will be happy. Unfortunately, Natasha does not know the Martians' divine digit yet.
Determine for which values $d$ Natasha can make the Martians happy.
Natasha can use only her banknotes. Martians don't give her change.
## Input
The first line contains two integers $n$ and $k$ ($1 \le n \le 100\,000$, $2 \le k \le 100\,000$) — the number of denominations of banknotes and the base of the number system on Mars.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — denominations of banknotes on Mars.
All numbers are given in decimal notation.
## Output
On the first line output the number of values $d$ for which Natasha can make the Martians happy.
In the second line, output all these values in increasing order.
Print all numbers in decimal notation.
[samples]
## Note
Consider the first test case. It uses the octal number system.
If you take one banknote with the value of $12$, you will get $14_8$ in octal system. The last digit is $4_8$.
If you take one banknote with the value of $12$ and one banknote with the value of $20$, the total value will be $32$. In the octal system, it is $40_8$. The last digit is $0_8$.
If you take two banknotes with the value of $20$, the total value will be $40$, this is $50_8$ in the octal system. The last digit is $0_8$.
No other digits other than $0_8$ and $4_8$ can be obtained. Digits $0_8$ and $4_8$ could also be obtained in other ways.
The second test case uses the decimal number system. The nominals of all banknotes end with zero, so Natasha can give the Martians only the amount whose decimal notation also ends with zero.
宇航员娜塔莎抵达了火星。她知道火星人是非常贫穷的外星人。为了确保火星公民更好的生活，他们的皇帝决定向每一位来访的游客征税。娜塔莎是地球居民，因此她必须支付税款才能进入火星领土。
火星上有 $n$ 种纸币面额：第 $i$ 种纸币的面值为 $a_i$。娜塔莎拥有每种面额的无限数量纸币。
火星人有 $k$ 根手指，因此他们使用以 $k$ 为基的数字系统。此外，火星人认为数字 $d$（在以 $k$ 为基的数字系统中）是神圣的。因此，如果娜塔莎所缴税额在以 $k$ 为基的数字系统中的最后一位是 $d$，火星人就会高兴。不幸的是，娜塔莎还不知道火星人的神圣数字是哪个。
请确定对于哪些值 $d$，娜塔莎能使火星人高兴。
娜塔莎只能使用她自己的纸币。火星人不会找零给她。
第一行包含两个整数 $n$ 和 $k$ ($1 lt.eq n lt.eq 100 thin 000$, $2 lt.eq k lt.eq 100 thin 000$) —— 纸币面额的数量和火星数字系统的基数。
第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$ ($1 lt.eq a_i lt.eq 10^9$) —— 火星纸币的面额。
所有数字均以十进制表示。
第一行输出娜塔莎能使火星人高兴的 $d$ 的值的个数。
第二行按升序输出所有这些值。
所有数字均以十进制表示。
考虑第一个测试用例。它使用八进制数字系统。
如果你取一张面值为 $12$ 的纸币，你会得到八进制下的 $14_8$。最后一位是 $4_8$。
如果你取一张面值为 $12$ 的纸币和一张面值为 $20$ 的纸币，总金额为 $32$。在八进制下，它是 $40_8$。最后一位是 $0_8$。
如果你取两张面值为 $20$ 的纸币，总金额为 $40$，这在八进制下是 $50_8$。最后一位是 $0_8$。
除了 $0_8$ 和 $4_8$ 之外，无法得到其他数字。$0_8$ 和 $4_8$ 也可以通过其他方式获得。
第二个测试用例使用十进制数字系统。所有纸币的面额都以零结尾，因此娜塔莎只能给出末尾也为零的金额。
## Input
第一行包含两个整数 $n$ 和 $k$ ($1 lt.eq n lt.eq 100 thin 000$, $2 lt.eq k lt.eq 100 thin 000$) —— 纸币面额的数量和火星数字系统的基数。第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$ ($1 lt.eq a_i lt.eq 10^9$) —— 火星纸币的面额。所有数字均以十进制表示。
## Output
第一行输出娜塔莎能使火星人高兴的 $d$ 的值的个数。第二行按升序输出所有这些值。所有数字均以十进制表示。
[samples]
## Note
考虑第一个测试用例。它使用八进制数字系统。如果你取一张面值为 $12$ 的纸币，你会得到八进制下的 $14_8$。最后一位是 $4_8$。如果你取一张面值为 $12$ 的纸币和一张面值为 $20$ 的纸币，总金额为 $32$。在八进制下，它是 $40_8$。最后一位是 $0_8$。如果你取两张面值为 $20$ 的纸币，总金额为 $40$，这在八进制下是 $50_8$。最后一位是 $0_8$。除了 $0_8$ 和 $4_8$ 之外，无法得到其他数字。$0_8$ 和 $4_8$ 也可以通过其他方式获得。第二个测试用例使用十进制数字系统。所有纸币的面额都以零结尾，因此娜塔莎只能给出末尾也为零的金额。
**Definitions**
Let $ n, k \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 100{,}000 $, $ 2 \leq k \leq 100{,}000 $.
Let $ A = \{a_1, a_2, \dots, a_n\} \subset \mathbb{Z}^+ $ with $ 1 \leq a_i \leq 10^9 $ be the set of banknote denominations.
Let $ R \subseteq \mathbb{Z}/k\mathbb{Z} $ be the set of residues modulo $ k $ achievable as a non-negative integer linear combination of the elements of $ A $:
$$
R = \left\{ \sum_{i=1}^n c_i a_i \mod k \,\middle|\, c_i \in \mathbb{Z}_{\geq 0} \right\}
$$
Let $ D \subseteq \{0, 1, \dots, k-1\} $ be the set of possible last digits in base-$ k $ representation of the tax amount, i.e.,
$$
D = R
$$
**Constraints**
- Natasha may use any non-negative number of each banknote (infinite supply).
- The tax amount must be a non-negative integer combination of $ a_1, \dots, a_n $.
- The last digit in base-$ k $ is the residue modulo $ k $.
**Objective**
Compute the set $ D \subseteq \{0, 1, \dots, k-1\} $ of achievable residues modulo $ k $, and output:
1. $ |D| $, the number of such residues.
2. The elements of $ D $ in increasing order.
**Key Insight**
The set $ D $ is the additive subgroup of $ \mathbb{Z}/k\mathbb{Z} $ generated by $ \{a_i \mod k \mid i = 1, \dots, n\} $.
Let $ g = \gcd(a_1, a_2, \dots, a_n, k) $. Then:
$$
D = \langle g \rangle = \{0, g, 2g, \dots, (\tfrac{k}{g} - 1)g\} \subseteq \mathbb{Z}/k\mathbb{Z}
$$
Thus, $ D = \{ m \cdot g \mod k \mid m \in \mathbb{Z} \} $, and $ |D| = \frac{k}{g} $.
API Response (JSON)
{
"problem": {
"name": "E. Border",
"description": {
"content": "Astronaut Natasha arrived on Mars. She knows that the Martians are very poor aliens. To ensure a better life for the Mars citizens, their emperor decided to take tax from every tourist who visited the",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1011E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Astronaut Natasha arrived on Mars. She knows that the Martians are very poor aliens. To ensure a better life for the Mars citizens, their emperor decided to take tax from every tourist who visited the...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "宇航员娜塔莎抵达了火星。她知道火星人是非常贫穷的外星人。为了确保火星公民更好的生活，他们的皇帝决定向每一位来访的游客征税。娜塔莎是地球居民，因此她必须支付税款才能进入火星领土。\n\n火星上有 $n$ 种纸币面额：第 $i$ 种纸币的面值为 $a_i$。娜塔莎拥有每种面额的无限数量纸币。\n\n火星人有 $k$ 根手指，因此他们使用以 $k$ 为基的数字系统。此外，火星人认为数字 $d$（在以 $k$ 为...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 100{,}000 $, $ 2 \\leq k \\leq 100{,}000 $. \nLet $ A = \\{a_1, a_2, \\dots, a_n\\} \\subset \\mathbb{Z}^+ $ with $ 1 \\leq a_i \\leq 10^9 $...",
"is_translate": false,
"language": "Formal"
}
]
}