题解 P4549 【裴蜀定理 / Min】

· · 题解

欢迎到家光顾我的博客

引言

这个题只要带着眼睛都知道要用到裴蜀定理(又叫做贝祖定理)。那么这个定理讲了啥呢？怎么证明？

裴蜀定理内容

### 证明 **首先声明一下，这个证明全靠我个人$YY$，所以可能有什么不合理的地方，如果有的话请看出来的$dalao$在评论区指明，O(∩_∩)O谢谢** 设${s=\gcd(a,b)}$，显然${s|a}$，并且${s|b}

又因为{x,y\in Z^*}

所以{s|ax,s|by}

显然要使得之前的式子成立，则必须满足c是a和b的公约数的倍数

又因为x和y是正整数

所以c必然是a,b最大公约数的倍数。

因此，证得该定理成立

针对这道题

上述裴蜀定理针对的是两个变量。那么我们很自然的就想到这样的定理能否推广到多个变量呢？显然可以，证明方法同上。

那这个题不就是推广后的定理的裸题吗QAQ。我们只需要对这所有的数字求一个\gcd，值得注意的是不要忘记数据中有负数，要将其变为正数再求\gcd。

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

inline int gcd(int x, int y) {
    return y ? gcd(y, x%y) : x;
}

int n;

int main() {
    scanf("%d", &n);
    int ans = 0, tmp;
    for(int i=1; i<=n; i++) {
        scanf("%d", &tmp);
        if(tmp < 0) tmp = -tmp;
        ans = gcd(ans, tmp);
    }
    printf("%d", ans);
}