【Alg】 扩展欧几里得算法

前言

扩展欧几里得算法是一个常用的数论算法，可以用于求解不定方程、线性同余方程、模意义下的乘法逆元等。

回顾普通欧几里得算法

大部分人初学算法肯定会接触到求最大公约数的欧几里得算法，它也叫做 「辗转相除法」。

它的求解过程十分简单：

int gcd(int a, int b) {
    if (b == 0) return a;         // 余数为 0，除尽了
    else return gcd(b, a % b);    // 大数模去小数，递归计算
}

原理不解释了。由此我们还可以得出每一层递归时的都是一样的（废话。

历史资料

欧几里得算法，又称辗转相除法，被认为是世界上最早的算法（公元前年）。辗转相除法首次出现于欧几里得的 《几何原本》 第 Ⅶ 卷，命题 Ⅰ 和 Ⅱ。

扩展欧几里得算法

首先我们需要知道 「裴蜀定理」：对于任意都存在满足（注意这里的可以为负）。

裴蜀定理的一个推论是，不定方程若存在合法解，则必定会有（可以理解为把都翻了几倍），也就是说最小为。

于是我们可以通过这种方法来判断不定方程是否有解。

但我还想知道在的情况下，解到底是多少（把这个解翻个若干倍就是其他解了，因为一定是的倍数）。

注意：扩展欧几里得算法算法只能解的不定方程。

它的实现方法是在普通欧几里得算法递归求回溯的时候顺带把算出来（因为要先求）。

计算的过程：我们在回溯到某一层的算出的都是关于当前层的满足（每一层的都一样）。

详细计算方法请看下面代码详解：

int exgcd(int a, int b, int &x, int &y) {  // 这里x和y都要被修改，所以使用引用参数
    if (!b) {							// b等于0，到达递归出口
        x = 1, y = 0;					// 此时的a为gcd，x=1,y=0可满足条件
        return a;
    }
    int res = exgcd(b, a % b, x, y);	// 存下gcd
    int t = x;							// 将下一层的x暂存下来
    x = y, y = t - a / b * y;			// 这个请看下面解释
    return res;
}

为什么 x = y, y = t - a / b * y; 推出来的可以满足条件呢？请看证明。

证明

设当前层要求的分别为，下一层已经求好了的分别为（回溯时从下往上推）。

则

由欧几里得定理可知：

故

又因为

将其代入式得

展开得

即

又因为，

且注意到与对应，与对应，

故。

以上证明过程来自 OI Wiki 扩展欧几里得算法 ，稍有改动。

最后我们要求不定方程的解时只需要这样调用：

int x, y;					// 因为是引用参数，所以x和y需要单独开变量
int d = gcd(a, b, x, y);	// 此时x和y里就是对应的解，d就是a和b的最大公因数