【模板】裴蜀定理

标签: #数论 #裴蜀定理 #最大公约数
原题目: luogu-P4549
简要描述: 裴蜀定理的应用，S的最小正值是所有A_i的绝对值的最大公约数。

1. 题目解析 (Problem Analysis)

题目要求我们找到一个整数序列 X={X1,…,Xn}X = \{X_1, \dots, X_n\}，使得线性组合 S=∑i=1nAi×XiS = \sum_{i=1}^n A_i \times X_i 的值是一个最小的正整数。

这是一个典型的数论问题，其核心与裴蜀定理（或称贝祖定理）紧密相关。

2. 核心思想 (Key Idea)

“裴蜀定理 (Bézout’s Identity)”

对于任意一组不全为零的整数 a1,a2,…,ana_1, a_2, \dots, a_n，存在一组整数 x1,x2,…,xnx_1, x_2, \dots, x_n，使得：

a1x1+a2x2+⋯+anxn=gcd⁡(a1,a2,…,an) a_1 x_1 + a_2 x_2 + \dots + a_n x_n = \gcd(a_1, a_2, \dots, a_n)
更进一步地，所有能够表示成 a1x1+⋯+anxna_1 x_1 + \dots + a_n x_n 形式的数，都是 gcd⁡(a1,…,an)\gcd(a_1, \dots, a_n) 的倍数。

根据裴蜀定理，题目中 SS 的所有可能取值，就是 gcd⁡(A1,A2,…,An)\gcd(A_1, A_2, \dots, A_n) 的所有倍数。 我们要找的是 SS 的最小正整数值。gcd⁡\gcd 本身就是正数，所以 SS 的最小正值就是 gcd⁡(A1,A2,…,An)\gcd(A_1, A_2, \dots, A_n) 本身。

处理负数

题目中 AiA_i 可能是负数。最大公约数的定义通常针对正整数，但我们可以利用性质 gcd⁡(a,b)=gcd⁡(∣a∣,∣b∣)\gcd(a, b) = \gcd(|a|, |b|)。因此，我们只需要求所有 AiA_i 的绝对值的最大公约数即可。

多个数的 GCD

多个数的最大公约数可以通过迭代计算得出：

gcd⁡(a1,a2,…,an)=gcd⁡(gcd⁡(a1,a2),a3,…,an) \gcd(a_1, a_2, \dots, a_n) = \gcd(\gcd(a_1, a_2), a_3, \dots, a_n)
我们可以用一个变量 ans 循环求解。

3. 算法步骤 (Algorithm Steps)

  1. 读入整数 nn。
  2. 初始化一个变量 ans。读入第一个数 A1A_1，令 ans = abs(A_1)。
  3. 从 i=2i=2 到 nn 循环，读入 AiA_i。
  4. 在循环中，更新 ans 的值为 gcd(ans, abs(A_i))。
  5. 循环结束后，ans 的值就是所有 ∣Ai∣|A_i| 的最大公约数，即为 SS 的最小值。
  6. 输出 ans。

4. 代码实现 (Code Implementation)

@@include-code(./1.cpp, cpp)

5. 复杂度分析 (Complexity Analysis)

  • 时间复杂度: O(Nlog⁡K)O(N \log K)，其中 NN 是序列的长度，KK 是序列中元素绝对值的最大值。 每次计算 gcd(a, b) 的时间复杂度是对数级别的，即 O(log⁡(min⁡(∣a∣,∣b∣)))O(\log(\min(|a|, |b|)))。我们需要进行 N−1N-1 次 gcd 计算。
  • 空间复杂度: O(1)O(1)。我们只需要常数级别的额外空间来存储变量。