P4549 【模板】裴蜀定理 题解
预备知识
Bézout 定理： 对于任意的
a,b (a,b∈Z)，都有相对应的
x,y (x,y∈Z) 使得
ax+by=gcd(a,b)。
证明：
考虑分类讨论。
在最后辗转相除到
b=0 时，可以使
x=1 和
y=0，使得
a×1+0×0=gcd(a,0)。
若
b>0，先假设存在
x,y (x,y∈Z)，满足
bx+y(amodb)=gcd(b,amodb)。
因为
bx+y(amodb)=bx+y(a−b⌊a÷b⌋)=ay+b(x−y⌊a÷b⌋)，所以我们令
x′=y 和
y′=x−y⌊a÷b⌋，即可知
ax′+by′=gcd(a,b)。
使用归纳法即可证明。
延伸定理
根据
gcd(a,b,c)=gcd(a,gcd(b,c)) 和刚刚证明的过程，可得
一般说该定理为 Bézout 定理的扩展定理。
题目分析
题目记
S=i=1∑nAi×Xi，根据 Bézout 定理的扩展定理可知
S=kgcd(A1,A2,⋯,Ai) (k∈Z) （易知
k 不影响等式成立）。明显地，
k=1 时可以存在
S>0 且取到最小值。所以，我们需要求的是
gcd(A1,A2,⋯,Ai)。
其实本题中
Ai 等价于
−Ai，因为可以更改系数
Xi 的正负，故我们计算时取
Ai 的绝对值。
代码
CPP#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：修改几处笔误。