P4549 题解

· · 题解

传送门：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）：

因此，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 by，因此 \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;
}