Description

---

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

Solution

---

裴蜀定理： 对于形如$ax+by=c$这样a、b、c都为正整数的不定方程，有解的条件是$gcd(a,b)|c$ 即当$c=gcd(a,b)$时取得最小正整数

本题我们可以两两合并，最后得到$S=k\cdot gcd(a_1,a_2...a_n)\left(k\in Z\right)$ 显然k取1的时候最小

Code

---

#include <stdio.h> #include <string.h> #include <algorithm> #define rep(i,st,ed) for (int i=st;i<=ed;++i) int gcd(int x,int y) { return !y?x:gcd(y,x%y); } int main(void) { int n,x; scanf("%d",&n); scanf("%d",&x); int GCD=x; rep(i,2,n) { scanf("%d",&x); GCD=gcd(x,GCD); } printf("%d\n", abs(GCD)); return 0; }