题解 P4549 【裴蜀定理 / Min】
奔波儿霸
2018-08-02 16:54:02
[欢迎到家光顾我的博客](https://www.cnblogs.com/bljfy/)
### 引言
这个题只要带着眼睛都知道要用到裴蜀定理(又叫做贝祖定理)。那么这个定理讲了啥呢？怎么证明？
### 裴蜀定理内容
${ax+by=c,x\in Z^*,y\in Z^*}$成立的充要条件是${\gcd(a,b)|c}$。$Z^*$表示正整数集。
### 证明
**首先声明一下，这个证明全靠我个人$YY$，所以可能有什么不合理的地方，如果有的话请看出来的$dalao$在评论区指明，O(∩_∩)O谢谢**
设${s=\gcd(a,b)}$，显然${s|a}$，并且${s|b}$
又因为${x,y\in Z^*}$
所以${s|ax,s|by}$
显然要使得之前的式子成立，则必须满足$c$是$a$和$b$的公约数的倍数
又因为$x$和$y$是正整数
所以$c$必然是$a,b$最大公约数的倍数。
因此，证得该定理成立
### 针对这道题
上述裴蜀定理针对的是两个变量。那么我们很自然的就想到这样的定理能否推广到多个变量呢？显然可以，证明方法同上。
那这个题不就是推广后的定理的裸题吗QAQ。我们只需要对这所有的数字求一个$\gcd$，值得注意的是不要忘记数据中有负数，要将其变为正数再求$\gcd$。
### 代码
```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
inline int gcd(int x, int y) {
return y ? gcd(y, x%y) : x;
}
int n;
int main() {
scanf("%d", &n);
int ans = 0, tmp;
for(int i=1; i<=n; i++) {
scanf("%d", &tmp);
if(tmp < 0) tmp = -tmp;
ans = gcd(ans, tmp);
}
printf("%d", ans);
}
```