扩展欧几里得算法

数学 丢番图 模板

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

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

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

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

实现：

• 初始化：设置初始值 $r_0=a,r_1=b$，同时设置系数 $s_0=1,s_1=0$ 和 $t_0=0,t_1=1$
• 执行辗转相除直到余数为0 (求gcd过程).对于每次迭代 $i$ :
  • 计算商$q_i=\lfloor r_i-2/r_i-1\rfloor$和余数$r_i=r_{i-2}-q_i{r}_{i-1}$
  • 更新系数$s_i=s_{i-2}-q_i{s}_{i-1}$和$t_i=t_{i-2}-q_i{t}_{i-1}$
• 结束条件：当某个余数 $r_n=0=0$ 时，前一个非零余数 $r_{n-1}$就是 $a$ 和 $b$ 的最大公约数，而对应的 $s_{n-1}$ 和 $t_{n-1}$即为满足等式的系数 $x$和 $y$

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;
}

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