[BZOJ 1441]Min（裴蜀定理）
Description
给出n个数(A1...An)现求一组整数序列(X1...Xn)使得S=A1*X1+...An*Xn>0,且S的值最小
Solution
裴蜀定理：
d
gcd(a,b)是ax+by可能取到的最小值
于是对于这道题求A1...An的gcd就可以了
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; int n,A,res; int gcd(int a,int b){return b?gcd(b,a%b):a;} int main() { scanf("%d",&n); scanf("%d",&res); for(int i=1;i<n;i++) { scanf("%d",&A); if(A<0)A=-A; res=gcd(res,A); } printf("%d ",res); return 0; }