数学：裴蜀定理

裴蜀定理也叫贝祖定理

说明了对任何整数a、b和它们的最大公约数d

关于未知数x和y的线性不定方程（称为裴蜀等式）

若a,b是整数,且（a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数
特别地，一定存在整数x,y，使ax+by=d成立

它的一个重要推论是：a,b互质的充要条件是存在整数x,y使ax+by=1

然后是推广到n个数的情况

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

特别来说，如果a1…an互质（不是两两互质）

那么存在整数x1……xn使得x1*a1+x2*a2+…xn*an=1

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

X我们可以不用管，只关心S就好了

知道结论S就是A中所有数的GCD，然后直接求就可以了

 1 #include<cstdio>
 2 #include<cmath>
 3 using namespace std;
 4 int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
 5 int n,ans;
 6 int main()
 7 {
 8     scanf("%d",&n);
 9     int x;
10     for(int i=1;i<=n;i++)
11     {
12         scanf("%d",&x);
13         ans=gcd(ans,x);
14     }
15     printf("%d",abs(ans));
16     return 0;
17 }