紫书太难了！简单易懂的GCD和扩展GCD

算法 数论

GCD

从前有一种神奇的算法叫做辗转相除法，它可以用来求两个数 a, b 的最大公约数（Greatest Common Divisor）。这个算法也简称gcd。

它的原理：$gcd(a,b) = gcd(b,a\%b)$ (a >= b, b != 0)。

证明：设 p 是 a,b 的一个公约数，$a = up, b = vp$ (u, v是整数）; $a\%b = a-kb = (u-kv)p$ , 则 p 是 a%b 的约数，所以 p 也是 b, a%b 的公约数。反之亦成立。所以 a, b, a%b 公约数相同，那么最大公约数也相同。

终止条件：当 b = 0 时，a, b 最大公约数是a。

代码实现（一行优雅的递归 =v=）：

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

扩展GCD

扩展GCD算法可以求出 $ax + by = gcd(a, b)$ 的其中一组整数解。（实际上这个方程有无数个整数解）。

一、如何求一组解？

$ax + by = gcd(a, b)$

设 x'、y' 满足：

$bx' + a\%by' = gcd(b, a\%b) = gcd(a, b)$

两式左侧相等，则

$ax + by = bx' + (a - [a/b]) y'$ （[a/b]为整除）

移项，得

$ax + by = ay' + b(x' - [a/b]y')$

俩'a'项相等，两'b'项相等，所以：

$x = y'$
$y = x' - [a/b]y$

这样不停递归下去，总要有终止条件，那就是b=0。

当b = 0时，

$ax + by = gcd(a,b) = a$

则 x = 1， y = 0。

直白的代码实现：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
void exgcd(int a, int b, int &d, int &x, int &y){
    //a、b为输入的a、b，d为gcd(a,b)
    //x、y传入外部变量的地址，直接修改（因为无法一下return俩变量）
    if(b == 0){
        d = a;
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a%b, d, x, y);
    int temp = x; 
    //暂时存一下x原先的值，以便接下来给y赋值的时候用
    x = y;
    y = temp - a / b * y;
}
int main(){
    int a, b, x, y, d;
    scanf("%d%d", &a, &b);
    exgcd(a, b, d, x, y);
    printf("%d * %d + %d * %d = %d", a, x, b, y, d);
    return 0;
}

更优(qí)雅(pā)的代码实现（来自紫书）：

int exgcd(int a, int b, int &d, int &x, int &y){
    if(b == 0){
        d = a;
        x = 1;
        y = 0;
    }
    else{
        gcd(b, a%b, d, y, x); //注意x和y调换了位置！
        y -= x * (a / b);
        //所以这个x是前一层的y’，这个y是前一层的x’
        //紫书真可怕
    }
}

二、一组整数解到手了，如何求所有整数解？

之前说过，这个方程有无数的整数解。但所幸这些解都可以用一组已知解表示！

我们已经得到一组解 $x_0、y_0$ ，设另外一组解为 $x_1、y_1$ 。

则：

$ax_0 + by_0 = ax_1 + by_1 = gcd(a, b)$

移项得：

$a(x_0 - x_1) = b(y_1 - y_0)$

由于a、b最大公约数是gcd(a, b)（以下简称g），等式两边同时除以g得：

$[a/g](x_0 - x_1) = [b/g](y_1 - y_0)$

此时的[a/g]与[b/g]是互质的，所以$(x_0 - x_1)是[b/g]的倍数，(y_1 - y_0)是[a/g]的倍数$。

设这个倍数是k，则：

$x_0 - x_1 = kb$
$y_1 - y_0 = ka$

移项得：

$x_1 = x_0 - kb$
$y_1 = ka + y_0$
（k取任意整数）

一点小补充：以上的证明过程其实跟最初的方程的“右侧”一点关系也没有，所以“右侧”不一定是gcd(a, b) , 是任意一个数都可以。换句话说，上面的等式也适用于一般的二元一次方程$ax + by = c$。

坚持看到这里的同学们……恭喜你们……

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈终于写完这一大串式子了！

等等，还没完！我们会求$ax + by = gcd(a, b)$的整数解了，那么……

三、如何求一般的二元一次方程$ax + by = c$ 的整数解？

这就很简单咯！

我们知道了一组解 $x_0,y_0$ 使 $ax_0 + by_0 = gcd(a, b)$, 那么等式两边同时除以gcd(a, b)再乘上c不就得出来了吗？

……等等，这么简单……有没有什么漏洞啊？

还真有。

我们要求的是$ax + by = c$的整数解，如果这个式子等式两边同时除以 gcd，则当c不是gcd的倍数时，右侧不是整数，而左边的a、b都是gcd的倍数，x、y又都是整数解，所以左侧是整数，左右两侧矛盾了。只有当c是gcd(a, b)的倍数时才有整数解。

当有解的时候上面的“简单”叙述才是可行的。根据该叙述，求出：

$x = x_0 * c / gcd(a, b)$
$y = y_0 * c / gcd(a, b)$

这时我们把扩展gcd求出的$x_0,y_0$我们就得出 $ax + by = c$ 的整数解了！

作者：胡小兔
批评指正敬请联系：yuanxiaodidl@163.com
打赏一根胡萝卜（真的吗？）：