提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

算法学习笔记(1): 欧几里得算法及其扩展

算法 笔记 学习
2023-03-20 15:30:29 时间

扩展欧几里得算法详解

目录

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

欧几里得算法

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

[gcd(a, b) = gcd(b, a \% b) ]

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

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

[gcd(a, b) = gcd(b, a-b) = gcd(b, a-kb) ]

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

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

[gcd(a, b) = gcd(b, a - b lfloor frac ab floor) = 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 - blfloor frac ab floor) ]

而边界条件是

[gcd(a, b) = gcd(c, 0) = c ]

则，在边界时有

[1 imes c + 0 imes 0 = c ]

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

但是我们要如何回推呢？

依据贝祖定理

[gcd(x, y) = sx + ty ]

以及

[gcd(a, b) = gcd(b, a - blfloor frac ab floor) ]

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

[egin{aligned} s_1 a + t_1 b &= s_2 b + t_2 (a - blfloor frac ab floor) \ &= t_2 a + (s_2 - t_2 lfloor frac ab floor)b end{aligned} ]

于是可以知晓

[egin{cases} s_1 = t_2 \ t_1 = s_2 - t_2 lfloor frac ab floor 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;
}

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

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

[egin{pmatrix} x_1 \ y_1 end{pmatrix} = egin{pmatrix} 0 & 1 \ 1 & -d_1 end{pmatrix} egin{pmatrix} x_2 \ y_2 end{pmatrix} ]

其中，(-d_1 = lfloorfrac ab floor)

于是，就可以一直乘下去

[egin{pmatrix} x \ y end{pmatrix} = egin{pmatrix} 0 & 1 \ 1 & -d_1 end{pmatrix} egin{pmatrix} 0 & 1 \ 1 & -d_2 end{pmatrix} egin{pmatrix} 0 & 1 \ 1 & -d_3 end{pmatrix} ldots egin{pmatrix} 0 & 1 \ 1 & -d_n end{pmatrix} egin{pmatrix} 1 \ 0 end{pmatrix} ]

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

设初始矩阵为M，则需要

[M egin{pmatrix} 0 & 1 \ 1 & -d_1 end{pmatrix} = egin{pmatrix} 0 & 1 \ 1 & -d_1 end{pmatrix} ]

所以

[M = egin{pmatrix} 1 & 0 \ 0 & 1 end{pmatrix} ]

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

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

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

则，(M)变为(egin{pmatrix} m_2 & m_1 - m_2d_k \ n_2 & n_1 - n_2d_kend{pmatrix})

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

相关文章