题解：P4549 【模板】裴蜀定理

shigengxin · 2025-05-15 21:42:39 · 题解

裴蜀定理

裴蜀定理是数论中的重要分块，其内容大致如下： 对于任意不全为零的整数 a 和 b，存在整数 x 和 y，使得：

将这个定理推广到多个整数的情况。对于 n 个整数 A_1,A_2,A_3,\ldots,A_n（不全为零），存在整数序列 X_1,X_2,X_3,\ldots,X_n 使得：

题目解析

题目要求我们找到一个整数序列 X，使得 S = \sum\limits_{i=1}^n A_i \times X_i 为正数，并且 S 尽可能小。根据定理，S 的最小正值就是所有 A_i 的绝对值的最大公约数。这是因为：

• 裴蜀定理告诉我们，S 可以取到 \gcd(A_1,A_2,A_3,\ldots,A_n) 的值。
• 任何 S 的正值都必须是 \gcd(A_1,A_2,A_3,\ldots,A_n) 的倍数（因为 \gcd 是所有 A_i 的线性组合的最小正值）。
• 因此，最小的正值 S 就是 \gcd 本身。

  解题步骤

• 计算所有 A_i 的绝对值的最大公约数 m。
• 最终的 m 就是答案。

  Code

  
  #include<bits/stdc++.h>
  using namespace std;
  int n, a;
  int gcdd(int a,int b){
  return (!b) ? a : gcd(b,a % b);//辗转相除法
  }

int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n; int m = 0; for (int i = 1; i <= n; ++i) { cin >> a; a = abs(a); m = gcdd(m, a); } cout << m; return 0; }

### 复杂度分析
* 时间复杂度：$O(n \cdot \log(\max(|A_i|)))$。
* 空间复杂度：$O(n)$。