学习裴蜀定理

主要参考：https://www.luogu.org/problemnew/solution/P4549

题目描述

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

输入格式

第一行给出数字N,代表有N个数下面一行给出N个数

输出格式

S的最小值

输入输出样例

输入 #1

2
4059 -1782

输出 #1

说明/提示

对于100%的数据，

　　没错，这个就是拓展欧几里得算法的模式，但是拓欧求解的方向不同，拓欧求解的方向是x,y，

　　这个的求解方向是，c。

　　裴蜀定理其实讲的就一个式子，

　　gcd（a,b） | c <=> ax + by = c , a b c 均属于 Z+

　　然后其实，这个题目，我们可以想到，ax+by，其实就是线性组合成的C，目前我们想要最小化C。

　　其实就是 ax + by = gcd(a,b)，此时x，y都是变量可以任意取值。

　　所以答案就是所有系数gcd一起。

 1 #include<cstdio>
 2 #include<algorithm>
 3 typedef long long ll;
 4 using namespace std;
 5 ll x;
 6 ll ans ;
 7 int n;
 8 ll gcd( ll a,ll b ){
 9     return b == 0 ? a : gcd(b,a%b);
10 }
11 int main()
12 {
13     scanf("%d",&n);
14     ll ans = 0;
15     for(int i=1;i<=n;i++){
16         scanf("%lld",&x);
17         if ( x < 0 ) x = -x ;
18         ans = gcd( x , ans );
19     }
20     return printf("%lld
",ans)*0;
21 }

裴蜀定理