裴蜀定理

裴蜀定理：

一定存在整数$x,y$，满足$ax+by=gcd(a,b)$

裴蜀定理推广：

一定存在整数$x,y$，满足$ax+by=gcd(a,b)*n$

裴蜀定理再推广：

$\text { 一定存在整数 } X_{1} \cdots X_{i} \text {, 满足 } \sum_{i=1}^{n} A_{i} X_{i}=\operatorname{gcd}\left(A_{1}, A_{2}, \cdots, A_{n}\right)$

题目

https://www.luogu.com.cn/problem/P4549 给定一个包含 $n$ 个元素的整数序列 $A$，记作 $A_1,A_2,A_3,...,A_n$。 求另一个包含 $n$ 个元素的待定整数序列 $X$，记 $S=\sum\limits_{i=1}^nA_i\times X_i$，使得 $S>0$ 且 $S$ 尽可能的小。

2
4059 -1782

99

对于 $100\%$ 的数据，$1 \le n \le 20$，$|A_i| \le 10^5$，且 $A$ 序列不全为 $0$。

思路

可以把这里的$X_i$看成$B_i$，例如$A_1*B_1+A_2*B_2=gcd(A1,A2)$,最后只需要求序列A的最小公倍数即可。

代码

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;

int gcd(int a,int b){
    return b? gcd(b,a%b):a;
}

int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    int n,s=0,a;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a;
        s = gcd(s,abs(a));
    }
    cout << s;
    return 0;
}