C++：编程实现扩展的欧几里得算法求逆元

在C++中，我们可以使用扩展的欧几里得算法（Extended Euclidean Algorithm）来计算两个整数的最大公约数（GCD）及其相对应的逆元，即满足a * b % m = 1的整数b。这是一个基于递归的算法，通常用于解决模反向乘法问题。

以下是一个简单的C++实现：

#include <iostream>

// 定义计算最大公约数和逆元的函数
std::pair<int, int> extendedEuclidean(int a, int m) {
    if (m == 0) {
        return {a, 1};
    } else {
        std::pair<int, int> result = extendedEuclidean(m, a % m);
        int x = result.second;
        int y = result.first - (a / m) * x;
        return {result.first, y};
    }
}

int main() {
    int a, m;
    std::cout << "Enter two integers: ";
    std::cin >> a >> m;

    // 计算逆元
    auto gcd_and_inverse = extendedEuclidean(a, m);
    int inverse = gcd_and_inverse.second;

    std::cout << "The inverse of " << a << " modulo " << m << " is " << inverse << ".\n";

    return 0;
}

在这个程序中，`extendedEuclidean` 函数会返回一个 `std::pair`，其中第一个元素是最大公约数，第二个元素是逆元。在`main`函数中，用户输入两个整数，然后调用这个函数并打印出结果。