小编点评

**目录扩展欧几里得算法详解** **欧几里得算法** 欧几里得算法是一种递归求最大公约数的方法。通过反复调用求最大公约数，我们可以不断地缩小两个数的差值，直到得到最大公约数。 **贝祖定理** 贝祖定理是欧几里得算法的一个推论。该定理表明，如果两个数的最大公约数为 s，那么存在两个整数 s1 和 s2，使它们的最大公约数为 s。 **扩欧** 扩欧是一种基于贝祖定理的算法，用于求解形如 ax + by = c 的二元一次等式的一组合法解。扩欧的核心思路是通过不断调整两数的相对位置，逐步缩小它们，直到找到它们的最小公约数。 **贝祖系数** 贝祖系数是扩欧算法中一个重要概念。它表示两个数的最大公约数的最小非负整数系数。在扩欧过程中，我们可以通过计算两个数的最大公约数的贝祖系数来推导出它们的最小公约数。 **扩欧的代码** 以下是一些实现扩欧的代码示例： ```python def exgcd(a, b): if b == 0: return a r = exgcd(b, a % b, t, s) t -= (a / b) * s return r def gcd(a, b): return b if b == 0 else gcd(b, a % b, t, s) ``` **扩欧的优化** 扩欧算法的效率与算法的复杂性有关。当两个数的最小公约数很大时，扩欧算法可能效率低下。因此，优化扩欧算法至关重要。 **结论** 扩欧是一种基于贝祖定理的算法，可以用于求解形如 ax + by = c 的二元一次等式的一组合法解。扩欧的代码可以通过优化来提高效率，但当两个数的最小公约数很大时，扩欧算法可能效率低下。

正文

扩展欧几里得算法详解

在了解扩欧之前我们应该先了解欧几里得算法

欧几里得算法

这是一个递归求最大公约数(greatest common divisor)的方法

可以通过一个类似的简单公式推导而来

好像叫做辗转相减法来着？

由于已知 \(a \mod b = a - b \lfloor \frac ab \rfloor\)

令 \(k = \lfloor \frac ab \rfloor\)则可以推导出

这里给出两种代码

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

// 这种方法稍微快了那么一点点。其实也没有什么影响
int gcd(int a, int b) {
    int t;
    while (b) {
        t = a % b, a = b, b = t;
    }
    return a;
}

---

但是在讲扩欧之前，还需要引入一个定理

贝祖定理

若\(a,b \in \mathbb{N^+}\)，则 \(\exists s, t\) 满足 \(gcd(a, b) = sa + tb\)

定义:

其中，\(s,t\)称为\(a, b\)的贝祖系数，等式 \(gcd(a, b) = sa + tb\) 称为贝祖恒等式

---

扩展欧几里得算法

本质上就是欧几里得算法和贝祖定理的结合产生的一种算法，可以用于求出形如

的二元一次等式的一组合法解（其中，\(a, b, c\)为参数）

在欧几里得算法中，核心的思路是这样的

而边界条件是

则，在边界时有

即可知，边界时应有\(s = 1, t = 0\)

但是我们要如何回推呢？

依据贝祖定理

以及

令等式左右的贝祖系数为\(s_1, t_1\)和\(s_2, t_2\)可以变形写出

于是可以知晓

于是，可以写出扩欧的代码

这里给出一种C-style的代码

int exgcd(int a, int b, int *s, int *t) {
    if (b == 0) {
        *s = 1, *t = 0;
        return a;
    }
    int r = exgcd(b, a % b, t, s);
    *t -= (a / b) * *s;
    return r;
}

当然，扩欧其实也是可以利用矩阵递推的

我们通过上述递推式可以将之转化为矩阵递推式

其中，\(-d_1 = \lfloor\frac ab\rfloor\)

于是，就可以一直乘下去

那么，有了从右向左的推导，从左向右呢？

设初始矩阵为M，则需要

所以

于是，我们可以简单的利用矩阵乘法递推了！

但是，如果真的用矩阵模拟还不如不用，所以我们还需要一定的优化

设当前矩阵\(M\)为\(\begin{pmatrix} m_1 & m_2 \\ n_1 & n_2 \end{pmatrix}\)，需要乘上\(\begin{pmatrix} 0 & 1 \\ 1 & -d_k \end{pmatrix}\)

则，\(M\)变为\(\begin{pmatrix} m_2 & m_1 - m_2d_k \\ n_2 & n_1 - n_2d_k\end{pmatrix}\)

所以，就按照上面的式子写就是了（我就不提供参考了）