前往：我自己搭建的博客
题目
洛谷P4549 裴蜀定理
题解
若a*x+b*y=c,当且仅当gcd(a,b)|c时有解，可推广到多个变量。
若A1*X1+A2*X2+A3*X3+……+An*Xn=S,当且仅当gcd(A1,A2,A3，……，An)|S时有解。
特别值得注意的是：gcd(0,a)=gcd(a,0)=|a|,gcd(-|a|,b)=gcd(|a|,b)，在运算过程中，负数可以直接转成正数。
题中要求最小的S，即求gcd。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,ans;
int gcd(int a,int b) {return b ? gcd(b,a%b) : a;}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x; scanf("%d",&x);
x=abs(x); ans=gcd(ans,x);
}
printf("%d\n",ans);
return 0;
}
