[文章目录]
Description
给出n个数A1 ~ An，求一组整数序列(X1...Xn)使得S=A1*X1+...An*Xn>0,且S的值最小
两个数a,b的xa+by的范围是gcd(a,b)的倍数，三个数就是相当于(a,b)和c的范围，那么就是gcd(gcd(a,b),c)的倍数。那么原题的解就是gcd(A1~An); 时间复杂度O(n) [连续和数取gcd的复杂度O(n+logw)]
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int gcd(int x,int y){return y?gcd(y,x%y):x;}
inline int Abs(int x){return x>0?x:-x;}
int main()
{
int n,x;
scanf("%d%d",&n,&x);
int now=Abs(x);
for(int i=2;i<=n;++i)
{
scanf("%d",&x);
now=gcd(now,Abs(x));
}
printf("%d",now);
return 0;
}