题解：CF1010C Border

形式化一下题意，就是求使得下式成立的 $r$ 的个数。

把 $r$ 看成定值，由裴蜀定理可知上式有解当且仅当

裴蜀定理可以推广到 $n$ 个整数的情形: 设 $a_1, a_2, \cdots, a_n$ 是不全为零的整数，则存在整数
$x_1, x_2, \cdots, x_n$ 使得 $a_1x_1 + a_2x_2 + \cdots + a_nx_n = \gcd(a_1, a_2, \cdots, a_n)$。

其逆定理也成立: 设 $a_1, a_2, \cdots, a_n$ 是不全为零的整数，$d > 0$ 是 $a_1, a_2, \cdots, a_n$ 的公约数，若存在整数 $x_1, x_2, \cdots, x_n$ 使 $a_1x_1 + a_2x_2 + \cdots + a_nx_n = d$，则 $d = \gcd(a_1, a_2, \cdots, a_n)$。
:::

设 $g = \gcd(a_1,a_2,\cdots,a_n)$，则可以改写成

其中 $g,k,r$ 为定值，因此移项可得

容易发现这就是 $ax + by = c$ 的变式，有解当且仅当

因此答案为 $\{\gcd(g,-k) \times 0,\gcd(g,-k) \times 1,\cdots,\gcd(g,-k) \times (m - 1)\}$，其中 $m = \lfloor\dfrac{k}{\gcd(g,-k)}\rfloor$。注意此处的 $\gcd$ 均为正数，可以在计算时直接去掉负号。

1
2
3
4
5
6
7
8
9
10

void solve ()
{
    int n = read (),k = read (),g = 0;
    vector <int> a (n + 1);
    for (int i = 1;i <= n;++i) a[i] = read (),g = __gcd (a[i],g);
    int tot = k / __gcd (g,k);
    printf ("%d\n",tot);
    for (int i = 0;i < tot;++i) printf ("%d ",i * __gcd (g,k));
    puts ("");
}