裴蜀定理

定理

若a,b是整数,且$gcd(a,b)=d$，那么对于任意的整数 x,y，$gcd(a,b)|ax+by $，特别地，一定存在整数x,y，使$ax+by=gcd(a,b)$成立。

逆定理-线性同余方程推广

P4549 【模板】裴蜀定理

//分析，在保证方程有解的情况下，ax+by=S，的最小结果是S=gcd(a,b) ,对其进行推广即是本题解法
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
	return b==0?a:gcd(b,a%b);
}
int main()
{
	ll n,a,b;
	cin>>n>>a;

	for(int i=2; i<=n; ++i)
	{
		cin>>b;
		a=gcd(a,b);
	}
	cout<<abs(a);
	return 0;
}