Nugine 的个人博客关于

扩展欧几里得递推算法

欧几里得算法

gcd(a,b)\mathrm{gcd}(a, b) 表示 整数 a 与 b 的最大公约数.

若 t=amod  bt = a \mod b, 则 gcd(a,b)=gcd(b,t)\mathrm{gcd}(a, b) = \mathrm{gcd}(b, t)

证明略.

递推版 gcd 算法

gcd 接受变量元组 (a,b)(a, b) 作为输入，输出最大公约数 (r)(r).

我们很难直接计算出 rr，但可以通过一些中间步骤逐步计算得到 rr.

我们定义一个中间状态

(c,  d,  t)(c,\;d,\;t)

其中 t=cmod  dt = c \mod d

定义一个状态转移过程，将一个状态映射到下一个状态.

(cdt)⇒(dtdmod  t)\begin{pmatrix} c\\ d\\ t\\ \end{pmatrix} \Rightarrow \begin{pmatrix} d\\ t\\ d\mod t\\ \end{pmatrix}

将初始状态赋值为 (a,  b,  amod  b)(a,\;b,\;a \mod b)，则 r=gcd(a,b)r = \mathrm{gcd}(a, b)

进行状态转移

(abamod  b)⇒(bamod  bbmod  (amod  b))\begin{pmatrix} a\\ b\\ a\mod b\\ \end{pmatrix} \Rightarrow \begin{pmatrix} b\\ a\mod b\\ b \mod (a\mod b)\\ \end{pmatrix}

此时

r=gcd(b,  amod  b)=gcd(a,  b)r = \mathrm{gcd}(b,\;a\mod b) = \mathrm{gcd}(a,\;b)

由归纳法可得，在任意一个中间状态 (c,d,t)(c, d, t) 时，有

r=gcd(c,d)r = \mathrm{gcd}(c, d)

状态转移不能无限进行下去，要有一个终止条件，即 t=0t = 0.

当 t=cmod  d=0t = c \mod d = 0 时，显然 d  ∣  cd\;|\;c， r=gcd(c,d)=dr = \mathrm{gcd}(c, d) = d.

在最终状态 (c,d,0)(c, d, 0) 时， dd 就是最大公约数 rr.

代码

int gcd(const int a, const int b) {
    int c = a, d = b, t = a % b;
    while (t) {
        c = d;
        d = t;
        t = c % d;
    }
    return d;
}

实际上，可以减少变量个数，直接使用输入时定义的变量 a, b 存放中间状态，即我们通常所见的 gcd 实现。

扩展欧几里得算法

设

r=gcd(a,b)=a⋅x+b⋅yr = \mathrm{gcd}(a, b) = a\cdot x + b\cdot y

则扩展欧几里得算法可以在求出 rr 的同时，得出二元一次方程r=a⋅x+b⋅yr = a \cdot x + b \cdot y 的一组整数解。

递推版 exgcd 算法

exgcd 是一个映射

(a, b)⇒(r, x, y)(a,\,b) \Rightarrow (r,\,x,\,y)

可以这样定义中间状态

(c, d, q, t, x, y)(c,\,d,\,q,\,t,\,x,\,y)

其中

q=⌊cd⌋t=cmod  d=a⋅x+b⋅y\begin{aligned} q &= \lfloor\frac{c}{d}\rfloor\\ t &= c \mod d = a \cdot x + b \cdot y\\ \end{aligned}

继承 gcd 的状态转移过程

(cdqtxy)⇒(dt⌊dt⌋dmod  tx′y′)\begin{pmatrix} c\\ d\\ q\\ t\\ x\\ y\\ \end{pmatrix} \Rightarrow \begin{pmatrix} d\\ t\\ \lfloor\frac{d}{t}\rfloor\\ d \mod t\\ x'\\ y'\\ \end{pmatrix}

当 dmod  t=0d \mod t = 0 时， r=gcd(c,d)=gcd(d,t)=tr = \mathrm{gcd}(c, d) = \mathrm{gcd}(d, t) = t.

此时该状态保证 r=t=a⋅x+b⋅yr = t = a \cdot x + b \cdot y， 即得解.

如何递推计算 x,yx, y ?

t=a⋅x+b⋅ydmod  t=a⋅x′+b⋅y′\begin{aligned} t &= a \cdot x + b \cdot y\\ d \mod t &= a \cdot x' + b \cdot y'\\ \end{aligned}dmod  t=d−⌊dt⌋⋅t=d−⌊dt⌋⋅(a⋅x+b⋅y)\begin{aligned} &d \mod t\\ = &d - \lfloor\frac{d}{t}\rfloor \cdot t\\ = &d - \lfloor\frac{d}{t}\rfloor \cdot (a \cdot x + b \cdot y)\\ \end{aligned}

无法计算 x′, y′x',\,y'.

又注意到上式中的 dd 阻断了递推，因此需要想办法用 x, yx,\,y 表示 dd.

这就是通常的 exgcd 递推算法.

定义状态

(c, d, q, t, x0, y0, x1, y1)(c,\,d,\,q,\,t,\,x_0,\,y_0,\,x_1,\,y_1)

其中

q=⌊cd⌋t=cmod  dc=a⋅x0+b⋅y0d=a⋅x1+b⋅y1\begin{aligned} q &= \lfloor\frac{c}{d}\rfloor\\ t &= c\mod d\\ c &= a\cdot x_0 + b\cdot y_0\\ d &= a\cdot x_1 + b\cdot y_1\\ \end{aligned}

状态转移

(cdqtx0y0x1y1)⇒(dt⌊dt⌋dmod  tx1y1x0−q⋅x1y0−q⋅y1)\begin{pmatrix} c\\ d\\ q\\ t\\ x_0\\ y_0\\ x_1\\ y_1\\ \end{pmatrix} \Rightarrow \begin{pmatrix} d\\ t\\ \lfloor\frac{d}{t}\rfloor\\ d\mod t\\ x_1\\ y_1\\ x_0-q\cdot x_1\\ y_0-q\cdot y_1\\ \end{pmatrix}

证明： 状态转移不会破坏状态定义

t=  c−q⋅d=  (a⋅x0+b⋅y0)−q⋅(a⋅x1+b⋅y1)=  (x0−q⋅x1)⋅a+(y0−q⋅y1)∗b\begin{aligned} &t\\ =\; &c - q \cdot d\\ =\; &(a \cdot x_0 + b \cdot y_0) - q \cdot (a \cdot x_1 + b \cdot y_1)\\ =\; &(x_0 - q \cdot x_1) \cdot a + (y_0 - q \cdot y_1) * b\\ \end{aligned}d=a⋅x1+b⋅y1t=a⋅(x0−q⋅x1)+b⋅(y0−q⋅y1)\begin{aligned} d &= a \cdot x_1 + b \cdot y_1\\ t &= a \cdot (x_0 - q \cdot x_1) + b \cdot (y_0 - q \cdot y_1)\\ \end{aligned}

因此转移后的状态仍满足定义。

初始状态

(a, b, ⌊ab⌋, amod  b, 1, 0, 0, 1)(a,\,b,\,\lfloor\frac{a}{b}\rfloor,\,a \mod b,\,1,\,0,\,0,\,1)

由归纳法可得，在任意一个中间状态，有 r=gcd(c,d)r = \mathrm{gcd}(c, d)

当 t=cmod  d=0t = c \mod d = 0 时, d ∣ c,  r=gcd(c, d)=dd\,|\,c,\;r = \mathrm{gcd}(c,\,d) = d.

r=d=a⋅x1+b⋅y1=a⋅x+b⋅yr = d = a \cdot x_1 + b \cdot y_1 = a \cdot x + b \cdot y

输出为 (d, x1, y1)(d,\,x_1,\,y_1)

代码

欧几里得算法: gcd.cpp

扩展欧几里得算法: exgcd.cpp

发布于 2019-02-01地址: GitHub, 知乎