裴蜀定理（又称贝祖定理）证明过程

对于任意整数 a, b，存在整数 x, y，使得：

$$ax+by=\gcd (a,b)$$

示例：

• 例如，对于方程 4x + 6y = 2，存在整数解 x = -1, y = 1。
• 而方程 4x + 6y = 3 则无整数解。

证明：

设 S 为形如 ax + by 的最小正整数，即：

$$S=a{x}_0+b{y}_0$$

其中 $x_0,y_0$ 为整数。

由于 $\gcd (a,b)\mid a$ 且 $\gcd (a,b)\mid b$，因此：

$$\gcd (a,b)\mid a{x}_0\text{且}\gcd (a,b)\mid b{y}_0$$

于是：

$$\gcd (a,b)\mid S\cdots \cdots (1)$$

接下来，我们考虑整数除法：

设 $a=qS+r$，其中 $0\le r<S$，则：

$$\begin{array}{rl}r& =a-qS\\ & =a-q(a{x}_0+b{y}_0)\\ & =a(1-q{x}_0)+b(-q{y}_0)\end{array}$$

注意到 $r$ 也可以表示为 $ax+by$ 的形式，而 $S$ 是形如 $ax+by$ 的最小正整数，因此必有 $r=0$。这说明 $S\mid a$。

同理可证 $S\mid b$。

因此，$S$ 是 $a$ 和 $b$ 的公约数，即：

$$S\mid \gcd (a,b)\cdots \cdots (2)$$

由 (1) 和 (2) 可知：

$$S=\gcd (a,b)$$

证毕。

裴蜀定理推广

存在整数 $x,y$，使得：

$$ax+by=\gcd (a,b)\cdot n$$

示例：

$$4x+6y=8,\text{整数解为 }x=-4,y=4$$

---

裴蜀定理再推广

存在整数 $X_1,X_2,\dots ,X_n$，使得：

$$\sum _{i=1}^n{A}_i{X}_i=\gcd (A_1,A_2,\dots ,A_n)$$

示例：

$$4x_1+6x_2+2x_3=4,\text{整数解为 }{x}_1=1,x_2=0,x_3=0$$

---

注意事项

• 若代入负数，欧几里得算法可能返回负数结果：

$$\gcd (8,-4)=-4$$

• 若系数为负数，可取绝对值计算最大公约数，不影响解的存在性：

$$\gcd (|A_1|,|A_2|,\dots ,|A_n|)$$

Luogu P4549 【模板】裴蜀定理

题目描述

给定一个包含 $n$ 个元素的整数序列 $A$，记作：

$$A_1,A_2,\dots ,A_n$$

求另一个包含 $n$ 个元素的待定整数序列 $X$，记：

$$S=\sum _{i=1}^n{A}_i\times X_i$$

使得 $S>0$ 且 $S$ 尽可能的小。

输入格式

第一行一个整数 $n$，表示序列元素个数。

第二行 $n$ 个整数，表示序列 $A$。

输出格式

一行一个整数，表示在 $S>0$ 的前提下，$S$ 的最小值。

数据范围

• $1\le n\le 20$
• $|A_i|\le 10^5$
• 序列 $A$ 不全为 $0$

思路：正如上面证明过程，只需要求解所有系数的最大公约数

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
void solve()
{
    int n, a, s;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a;
        s = gcd(s, abs(a));
    }
    cout << s;
}