传送门：P4549 【模板】裴蜀定理

更佳的阅读体验：洛谷 P4549 题解

算法介绍

给定一个长度为 $n$ 的整数序列 $A$ 和一个待定整数序列 $X$，求 $S = \sum \limits_{i = 1}^{n} A_i \times X_i$ 在正数范围内的最小值。

看上去似乎有点无从下手。

那先从简单的开始！我们来考虑 $n = 2$ 的情况，此时问题简化为求 $A_1 X_1 + A_2 X_2$ 的最小值。

如果我们设 $a, b$ 是不全为 $0$ 的整数，那么有裴蜀定理（Bézout's Lemma）：

• 对于任意整数 $x, y$，有 $\gcd (a, b) \mid (ax + by)$。
• 存在整数 $x, y$，使得 $ax + by = \gcd (a, b)$。

因此，$ax + by$ 的最小正整数值显然是 $\gcd (a, b)$。上述问题的答案就是 $\gcd(A_1, A_2)$。

那么，当 $n \ge 3$ 呢？我们尝试推广裴蜀定理。

假设有三个整数 $a, b, c$。我们首先对前两个数应用裴蜀定理，存在整数 $x_1, x_2$，使得 $ax_1 + bx_2 = \gcd (a, b)$。接下来，将这个结果与第三个数 $c$ 结合，即存在整数 $k, x_3$，使得 $\gcd (a, b) \times k + cx_3 = \gcd( \gcd(a, b), c)$。

我们知道，最大公约数有性质：$\gcd (a, b, c) = \gcd (\gcd(a, b), c)$，因此存在整数组合使得 $ax_1 + bx_2 + cx_3 = \gcd(a, b, c)$，且不存在更小的正数解。

这样推广下去，最终无论 $n$ 的大小，问题的最小正数解都是所有 $A_i$ 的最大公约数的绝对值。因此，我们只需要计算整个序列 $A$ 的最大公约数，并取其绝对值即可。

正确性证明

我们设 $a, b$ 是不全为 $0$ 的整数，那么一定有 $\gcd(a, b) \mid a$ 且 $\gcd(a, b) \mid b$。设 $x, y$ 为整数，则有 $\gcd(a, b) \mid ax$ 且 $\gcd(a, b) \mid bx$，因此 $\gcd(a, b) \mid (ax + by)$。

对于定理的第二点，若 $a$ 和 $b$ 任意一个等于 $0$，则 $\gcd(a, b)$ 的值为非零数的值，此时定理显然成立。

若 $ab \neq 0$，由于 $\gcd(a, b) = \gcd(a, -b)$，我们不妨设 $a, b$ 都大于 $0$，$a \ge b$，且有 $\gcd(a, b) = d$。

对 $ax + by = d$，两边同时除以 $d$，得到 $a_1x + b_1y = 1$，其中 $a_1, b_1$ 互质。接下来证明 $a_1x + b_1y = 1$。

我们先来回顾一下辗转相除法：$\gcd(a, b) \rightarrow \gcd(b, a \bmod b) \rightarrow \cdots$。我们把模出来的数记作 $r$，则有：

$$ \gcd(a_1, b_1) = \gcd(b_1, r_1) = \gcd(r_1, r_2) = \cdots = \gcd(r_{n - 1}, r_n) = 1 $$

把辗转相除法中的运算展开成带余除法，得到：

$$ \begin{align*} a_1 & = q_1b_1 + r_1 & (0 \le r_1 < b_1) \\ b_1 & = q_2r_1 + r_2 & (0 \le r_2 < r_1) \\ r_1 & = q_3r_2 + r_3 & (0 \le r_3 < r_2) \\ & \cdots & \\ r_{n - 3} & = q_{n - 1}r_{n - 2} + r_{n - 1} & \\ r_{n - 2} & = q_nr_{n - 1} + r_n & \\ r_{n - 1} & = q_{n + 1}r_n \end{align*} $$

我们令辗转相除法在除到互质的时候退出，则 $r_n = 1$，所以有：

$$ r_{n - 2} = q_nr_{n - 1} + 1 $$

即：

$$ 1 = r_{n - 2} - q_nr_{n - 1} $$

用倒数第三个式子 $r_{n - 1} = r_{n - 3} - q_{n - 1}r_{n - 2}$ 代入上式，得：

$$ 1 = (1 + q_nq_{n - 1}) r_{n - 2} - q_nr_{n - 3} $$

然后用同样的办法逐个地消去 $r_{n - 2}, \cdots, r_1$，即可证得 $1 = a_1x + b_1y$。

代码实现

#include <iostream>
#include <algorithm>
using namespace std;

int n, a, ans;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> a;
    ans = a;
    for (int i = 2; i <= n; ++i)
        cin >> a, ans = __gcd(ans, abs(a));
    cout << ans << '\n';
    return 0;
}