题解 P4549 【【模板】裴蜀定理】

· · 题解

首先，介绍裴蜀定理及其证明。

裴蜀定理

若a,b是整数,且\gcd(a,b)=d，那么对于任意的整数x,y，ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。（看了一下，貌似没有题解写到后面加粗部分的证明？）

证明：

首先，易知d\mid a且d\mid b，由整除性质可知\forall x,y \in \mathbb Z，d\mid ax+by。

令p为ax+by的最小正整数值，q=\lfloor \dfrac{a}{p}\rfloor，r=a\mod p = a - qp=a-q(ax+by)=a(1-qx)+bqy，可知r也是a,b的线性组合（ax+by的一种形式）。因为p是ax+by的最小正值，0\le r < p，故r=0，即p\mid a.

同理，我们可以证得p\mid b。

因为所有ax+by都是d的倍数，故p=d。证毕

将裴蜀定理推广到本题上，可知\forall A_iX_i+A_{i+1}X_{i+1}，其最小正整数的值为\gcd(A_i,A_{i+1})。由于\gcd(a_1,a_2\dots,a_n)=\gcd(\gcd(a_1,a_2\dots,a_{n-1}),a_n)，故可以递推求整个序列的\gcd。遇到负数时求其相反数即可。

代码如下

#include <cstdio>

int n, a, ans;

int gcd(int x, int y) {//辗转相除法求gcd
    return !y ? x : gcd(y, x % y);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a);
        a = a > 0 ? a : -a;//遇到负数时求相反数
        ans = gcd(ans, a);//递推求整个序列的gcd
    }
    return !printf("%d\n", ans);
}

目前本题的大部分题解都只证明了\gcd(a,b)\mid ax+by，而忽略了为什么\exists ax+by=\gcd(a,b)。希望大家能够细心对待每一题，避免”想当然“的情况出现。