题解：P4549 【模板】裴蜀定理
0Io_oI0
·
·
题解
内容
# 证明
我们可以先只考虑 $ax+by=1$ 的解。
1. 若 $\gcd(a,b)=d>1$ 则左右模 $d$ 不同余。
对于 $ax+by=c$ 若 $d$ 不为 $c$ 的因子则同样无解。
2. 若 $\gcd(a,b)=1$ 则我们考虑 $ax+by=1$ 左右同时模 $b$ 有 $ax\equiv 1(\mathrm{mod}\ b)$，因为 $\left\{1,2,\dots,b \right\}$ 为模 $b$ 的完系，且 $\gcd(a,b)=1$，所以 $\left\{a,2a,\dots,ab\right\}$ 也为模 $b$ 的完系。所以必存在 $x_0∈\left\{1,2,\dots,b\right\}$ 使得 $ax_0\equiv 1(\mathrm{mod}\ b)$。我们可以记 $ax_0=1+kb$ 代入 $ax+by=1$ 有 $y=-k$。所以 $ax+by=1$ 有整数解。到这里我们可以发现其实这也就相当于 $ax+by=c$ 有整数解，因为你把 $ax+by=1$ 的整数解乘上 $c$ 就好了。
这样充分性就证明完毕了！
接下来上代码：
```cpp
#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi 0
#define i_will signed
#define ak main
#define IMO ()
#define int long long
#define double long double
I AK IOI;
int n,ans,x;
i_will ak IMO{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//freopen("","r",stdin);
//freopen("","w",stdout);
cin>>n>>ans;
ans=abs(ans);
while(n--){
cin>>x;
ans=__gcd(ans,abs(x));
}
cout<<ans;
i_ak ioi;
}
```
亲测可过，请勿抄袭！