洛谷 P4549 【模板】裴蜀定理

题目

题目描述

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

输入格式

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

输出格式

S的最小值

输入输出样例

输入 #1复制

2
4059 -1782

输出 #1

99

说明/提示

对于100%的数据，1 le n le 201≤n≤20，|x_i| le 100000∣xi​∣≤100000

 

分析

• 首先，肯定是用这个定理啦

• 这个定理是 ax+by=c c|gcd（a,b）
• 所以两个数的最小整数解肯定是两数的gcd
• 那么多个数
• 就是多个数的gcd啦

 

代码

#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    if (b==0) return a;
    gcd(b,a%b);
}
int main ()
{
    int n,ans=0;
    cin>>n;
    for (int i=1,x;i<=n;i++)
    {
        cin>>x;
        if (x<0)
          x=-x;
        ans=gcd(ans,x);
    } 
    cout<<ans;
}