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

· · 题解

P4549 【模板】裴蜀定理 题解

预备知识

Bézout 定理： 对于任意的 a, b\ (a,b\in \Z)，都有相对应的 x, y\ (x,y\in \Z) 使得 ax + by = \gcd(a, b)。

证明：

考虑分类讨论。

在最后辗转相除到 b = 0 时，可以使 x = 1 和 y = 0，使得 a\times 1 + 0\times 0 = \gcd(a, 0)。

若 b > 0，先假设存在 x, y\ (x,y\in \Z)，满足 bx + y(a\bmod b) = \gcd(b,a\bmod b)。

因为 bx + y(a\bmod b) = bx + y(a - b\lfloor a\div b\rfloor) = ay + b(x - y\lfloor a\div b\rfloor)，所以我们令 x' = y 和 y' =x-y\lfloor a\div b\rfloor，即可知 ax' + by' = \gcd(a,b)。

使用归纳法即可证明。

延伸定理

根据 \gcd(a, b, c) = \gcd(a, \gcd(b, c)) 和刚刚证明的过程，可得

a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = \gcd(a_1, a_2, \dots,a_n) \\ (a, x\in \Z) \\ \text{即}\sum\limits_{i=1}^na_i\times x_i = \gcd(a_1, a_2, \dots,a_n)

一般说该定理为 Bézout 定理的扩展定理。

题目分析

题目记 S=\sum\limits_{i=1}^nA_i\times X_i，根据 Bézout 定理的扩展定理可知 S = k\gcd(A_1, A_2, \cdots,A_i)\ (k\in \Z) （易知 k 不影响等式成立）。明显地，k = 1 时可以存在 S > 0 且取到最小值。所以，我们需要求的是 \gcd(A_1, A_2, \cdots,A_i)。

其实本题中 A_i 等价于 -A_i，因为可以更改系数 X_i 的正负，故我们计算时取 A_i 的绝对值。

代码

#include<bits/stdc++.h>
using namespace std;
int n,ans;
signed main(void){
    scanf("%d",&n);
    n--;
    scanf("%d",&ans);
    ans=abs(ans);
    while(n--){
        int x;
        scanf("%d",&x);
        ans=__gcd(ans,abs(x));
    }printf("%d\n",ans);
    return 0;
}

感谢大家的浏览，希望得到大家的认可与支持。

Update250604：修改几处笔误。