裴蜀定理板子|曾子愚 's Blog

P4549 【模板】裴蜀定理 - 洛谷题解

原文链接

问题分析

我们需要找到一个整数序列 $X$ ，使得
$S = \sum\limits_{i=1}^n A_i \times X_i$
满足 $S > 0$ 并且尽可能小。换句话说，我们要在所有可能的满足条件的 $S$ 中找到最小的正整数。

这个问题实际上可以转化为一个数论问题：找到序列 $A$ 的元素通过整数线性组合能够表示的最小正整数。这一最小正整数恰好是序列 $A$ 所有元素的最大公约数（GCD）。

数学证明

对于给定的整数序列 $A = [A_1, A_2, \ldots, A_n]$ ，存在以下性质：

线性组合性质： $S = \sum\limits_{i=1}^n A_i \times X_i$ 的所有可能取值的最小正整数是 $A_1, A_2, \ldots, A_n$ 的最大公约数。
存在性：根据裴蜀定理（贝祖定理），对于任意的整数序列 $A$ ，存在整数 $X_i$ 使得 $S = \gcd(A_1, A_2, \ldots, A_n)$ 。

因此，要求的最小正整数 $S$ 就是序列 $A$ 的所有元素的绝对值的最大公约数。

实现步骤

输入处理：
- 读取整数 $n$ ，表示序列 $A$ 的长度。
- 读取序列 $A$ 的 $n$ 个整数。
计算最大公约数：
- 将序列 $A$ 中的每个元素取绝对值，因为最大公约数定义在非负整数上。
- 使用辗转相除法（欧几里得算法）逐步计算序列中所有元素的最大公约数。
输出结果：
- 输出计算得到的最大公约数，即为满足 $S > 0$ 且最小的 $S$ 。

代码解析

以下是根据上述思路实现的 C++ 代码：

#include <cstdlib>
#include <iostream>

// 计算两个整数的最大公约数
int gcd(int a, int b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

// 模板函数，用于取绝对值
template<class T>
void abss(T &t){
    t = abs(t);
}

int main(){
    int n;
    std::cin >> n; // 输入序列长度

    int tmpa, tmpb;
    std::cin >> tmpa; // 输入第一个元素
    abss(tmpa); // 取绝对值

    // 逐个输入剩余元素并计算最大公约数
    for(int i = 1; i < n; i++){
        std::cin >> tmpb;
        abss(tmpb);
        tmpa = gcd(tmpa, tmpb);
    }

    std::cout << tmpa << "\n"; // 输出结果
}

代码说明：

gcd 函数：使用递归实现欧几里得算法，用于计算两个数的最大公约数。
abss 函数模板：将传入的数取绝对值，确保所有参与 GCD 计算的数都是非负的。
主函数：
- 首先读取序列的长度 $n$ 。
- 然后读取第一个元素，取绝对值后存储在 tmpa 中。
- 接着循环读取剩余的 $n-1$ 个元素，每读取一个元素就取绝对值并更新 tmpa 为当前 tmpa 与新元素的 GCD。
- 最终，tmpa 就是所有元素的最大公约数，输出该值。

举例说明

样例输入：

2
4059 -1782

计算过程：

取绝对值后，序列变为 [4059, 1782]。
计算 GCD：
- gcd(4059, 1782)：
  - 4059 ÷ 1782 = 2 余 495
  - gcd(1782, 495)
- gcd(1782, 495)：
  - 1782 ÷ 495 = 3 余 297
  - gcd(495, 297)
- gcd(495, 297)：
  - 495 ÷ 297 = 1 余 198
  - gcd(297, 198)
- gcd(297, 198)：
  - 297 ÷ 198 = 1 余 99
  - gcd(198, 99)
- gcd(198, 99)：
  - 198 ÷ 99 = 2 余 0
  - 结果为 99