扩展欧几里得算法

扩展欧几里得算法（Extended Euclidean Algorithm）是在经典的欧几里得算法的基础上，除了求解两个整数的最大公约数（GCD）之外，还能够求解贝祖定理（Bézout’s identity）的整数解。贝祖定理表明，对于任意两个整数 a 和 b，它们的最大公约数 ddd 可以表示为：d=ax+by

其中，x 和 y 是整数。

扩展欧几里得算法通过递归地在计算GCD的同时追踪这些系数x 和 y，从而求出贝祖定理中的解。

扩展欧几里得算法的步骤：

基础情况：如果 b=0，则 a 即为最大公约数，此时 x=1, y=0。
递归计算：若 b≠0 ，则进行以下递归步骤：
- 计算 a÷b的商 q 和余数 r，即 a=bq+r。
- 递归地调用扩展欧几里得算法来计算 b 和 r 的GCD，同时得到对应的系数 x₁和 y₁使得 GCD(b,r)=bx₁+ry₁。
- 由于 r=a−bq，可以通过 x=y₁ 和 y=x₁−qy₁ 得到对应 a 和 b 的系数。

代码演示：

/**************************************************************** 
 * Description: 扩展欧几里得算法
 * Author: Alex Li
 * Date: 2024-08-15 07:38:33
 * LastEditTime: 2024-08-15 07:38:41
****************************************************************/
#include <iostream>

// 扩展欧几里得算法
int extended_gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1; // 当 b 为 0 时，x 取 1，y 取 0
        y = 0;
        return a; // 此时最大公约数为 a
    }

    int x1, y1; // 用于存储递归调用的结果
    int gcd = extended_gcd(b, a % b, x1, y1); // 递归调用

    // 根据递归返回的结果，更新当前 x 和 y 的值
    x = y1;
    y = x1 - (a / b) * y1;

    return gcd; // 返回最大公约数
}

int main() {
    int a, b;
    std::cout << "请输入两个整数 a 和 b: ";
    std::cin >> a >> b;

    int x, y;
    int gcd = extended_gcd(a, b, x, y);

    std::cout << "GCD(" << a << ", " << b << ") = " << gcd << std::endl;
    std::cout << "贝祖定理解: x = " << x << ", y = " << y << std::endl;
    std::cout << "验证: " << a << " * " << x << " + " << b << " * " << y << " = " << gcd << std::endl;

    return 0;
}

Previous Lesson

Back to Lesson

Next Topic

数据结构与算法

扩展欧几里得算法

扩展欧几里得算法的步骤：