Description

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

Solution

裴蜀定理：

显然gcd(a,b)|(ax+by),所以如果ax+by=d存在整数解的话必然有gcd(a,b)|d

gcd(a,b)是ax+by可能取到的最小值

于是对于这道题求A1...An的gcd就可以了

#include
     
      #include
      
       #include
       
        #include
        
         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