[BZOJ1441]Min

题面：Please contact lydsy2012@163.com!

 

给出n个数(A1...An)现求一组整数序列(X1...Xn)使得S=A1*X1+...An*Xn>0,且S的值最小

 

由裴蜀定理，

设a1,a2,a3......an为n个整数，d是它们的最大公约数，那么存在整数x1......xn使得x1*a1+x2*a2+...xn*an=d。

 

那么求这n个数的|gcd|就行了。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long gcd(long long x,long long y) {return x?gcd(y%x,x):y;}
long long a,b,n;
int main() {
    scanf("%lld%lld",&n,&a);n--;
    while(n--) {
        scanf("%lld",&b);
        a=gcd(a,b);
    }
    if(a<0) a=-a;
    printf("%lld",a);
    return 0;
}