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 \le n \le 10^5 $, $ 2 \le k \le 10^5 $.
Let $ A = \{a_1, a_2, \dots, a_n\} \subset \mathbb{Z}^+ $ be the set of banknote denominations.
Let $ S = \left\{ \sum_{i=1}^n c_i a_i \,\middle|\, c_i \in \mathbb{Z}_{\ge 0} \right\} $ be the set of all non-negative integer linear combinations of the denominations.
Let $ R = \{ x \bmod k \mid x \in S \} \subseteq \mathbb{Z}/k\mathbb{Z} $ be the set of possible residues modulo $ k $ achievable by sums of banknotes.
**Constraints**
1. $ 1 \le a_i \le 10^9 $ for all $ i \in \{1, \dots, n\} $
2. All computations are performed in integer arithmetic modulo $ k $.
**Objective**
Compute the set $ R \subseteq \{0, 1, \dots, k-1\} $, i.e., the set of all possible last digits $ d \in \mathbb{Z}/k\mathbb{Z} $ in base-$ k $ representation of achievable tax amounts.
Output:
- The cardinality $ |R| $,
- The elements of $ R $ in increasing order.
**Note:**
The set $ R $ equals the additive subgroup of $ \mathbb{Z}/k\mathbb{Z} $ generated by $ \{ a_i \bmod k \mid i = 1, \dots, n \} $.
Let $ g = \gcd(a_1, a_2, \dots, a_n, k) $. Then $ R = \langle g \rangle = \{ 0, g, 2g, \dots, (k/g - 1)g \} \subseteq \mathbb{Z}/k\mathbb{Z} $.
API Response (JSON)
{
"problem": {
"name": "C. 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": "CF1010C"
},
"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 \\le n \\le 10^5 $, $ 2 \\le k \\le 10^5 $. \nLet $ A = \\{a_1, a_2, \\dots, a_n\\} \\subset \\mathbb{Z}^+ $ be the set of banknote denominations. \n\nLet ...",
"is_translate": false,
"language": "Formal"
}
]
}