imicola 扩展欧几里得算法
扩展欧几里得算法

扩展欧几里得算法

356 字 · 约 1 分钟

扩展欧几里得算法(Extended Euclidean Algorithm)

扩展欧几里得算法是基于经典的欧几里得算法,用于计算两个整数 a和 b的最大公约数,同时还能够找到一组整数系数 x和 y,使得以下等式成立:

ax+by=gcd⁡⁡(a,b)ax+by=\gcd⁡(a,b)

上式是一个典型的线性丢番图方程,其实扩展欧几里得算法也常用于计算线性丢番图方程的一组特解

实现:

  • 初始化:设置初始值 r0=a,r1=br_0=a, r_1=b,同时设置系数 s0=1,s1=0s_0=1, s_1=0 和 t0=0,t1=1t_0=0, t_1=1
  • 执行辗转相除直到余数为0 (求gcd过程).对于每次迭代 ii :
    • 计算商qi=⌊ri−2/ri−1⌋q_i = \lfloor{r_i-2/r_i-1}\rfloor和余数ri=ri−2−qiri−1r_i = r_{i-2} - q_ir_{i-1}
    • 更新系数si=si−2−qisi−1s_i = s_{i-2}-q_is_{i-1}和ti=ti−2−qiti−1t_i = t_{i-2}-q_it_{i-1}
  • 结束条件:当某个余数 rn=0=0r_n=0=0 时,前一个非零余数 rn−1r_{n−1}就是 aa 和 bb 的最大公约数,而对应的 sn−1s_{n−1} 和 tn−1t_{n−1}即为满足等式的系数 xx和 yy
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a; // 返回gcd(a, b)
    }
    int r = exgcd(b, a % b, x, y);
    int t = y;
    y = x - (a / b) * y;
    x = t;
    return r;
}
cpp

上述代码中传入参数x,y最后会变为一组特解,返回的r是a,b的最大公因数

知识关联

2 反向链接 · 1 提及笔记
局部关系图谱 悬停高亮 · 点击跳转