内容

证明

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$ 就好了。

#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;
}