扩展欧几里得算法详解

[TOC]

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

欧几里得算法

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

$$\gcd(a, b) = \gcd(b, a \% b) $$

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

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

$$\gcd(a, b) = \gcd(b, a-b) = \gcd(b, a-kb) $$

由于已知 $a \bmod b = a - b \lfloor \frac ab \rfloor$

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

$$\gcd(a, b) = \gcd(b, a - b \lfloor \frac ab \rfloor) = \gcd(b, a \% b) $$

这里给出两种代码

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$ 称为贝祖恒等式

扩展欧几里得算法

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

$$ax + by = c $$

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

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

$$\gcd(a, b) = \gcd(b, a \% b) = \gcd(b, a - b\lfloor \frac ab \rfloor) $$

而边界条件是

$$\gcd(a, b) = \gcd(c, 0) = c $$

则，在边界时有

$$1 \times c + 0 \times 0 = c $$

即可知，边界时应有$s = 1, t = 0$

但是我们要如何回推呢？

依据贝祖定理

$$\gcd(x, y) = sx + ty $$

以及

$$\gcd(a, b) = \gcd(b, a - b\lfloor \frac ab \rfloor) $$

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

$$\begin{aligned} s_1 a + t_1 b &= s_2 b + t_2 (a - b\lfloor \frac ab \rfloor) \\ &= t_2 a + (s_2 - t_2 \lfloor \frac ab \rfloor)b \end{aligned} $$

于是可以知晓

$$\begin{cases} s_1 = t_2 \\ t_1 = s_2 - t_2 \lfloor \frac ab \rfloor \end{cases} $$

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

这里给出一种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;
}

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

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

$$\begin{pmatrix} x_1 \\ y_1 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & -d_1 \end{pmatrix} \begin{pmatrix} x_2 \\ y_2 \end{pmatrix} $$

其中，$-d_1 = \lfloor\frac ab\rfloor$

于是，就可以一直乘下去

$$\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & -d_1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -d_2 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -d_3 \end{pmatrix} \ldots \begin{pmatrix} 0 & 1 \\ 1 & -d_n \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} $$

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

设初始矩阵为M，则需要

$$M \begin{pmatrix} 0 & 1 \\ 1 & -d_1 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & -d_1 \end{pmatrix} $$

所以

$$M = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} $$

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

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

设当前矩阵$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}$

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