C++欧几里得算法和扩展欧几里得算法

欧几里得算法（Euclidean Algorithm）和扩展欧几里得算法（Extended Euclidean Algorithm）是用于求解最大公约数和线性方程的经典算法。下面我将为您提供 C++ 的实现示例。

1. 欧几里得算法（GCD）：

#include <iostream>

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {
    int a = 54;
    int b = 24;
    int result = gcd(a, b);
    std::cout << "GCD(" << a << ", " << b << ") = " << result << std::endl;
    return 0;
}

输出：

GCD(54, 24) = 6

1. 扩展欧几里得算法：

#include <iostream>

int extendedGcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    int x1, y1;
    int gcd = extendedGcd(b, a % b, x1, y1);

    x = y1;
    y = x1 - (a / b) * y1;

    return gcd;
}

int main() {
    int a = 54;
    int b = 24;
    int x, y;
    int gcd = extendedGcd(a, b, x, y);
    std::cout << "GCD(" << a << ", " << b << ") = " << gcd << std::endl;
    std::cout << "x = " << x << ", y = " << y << std::endl;
    return 0;
}

输出：

GCD(54, 24) = 6
x = 1, y = -2

在扩展欧几里得算法中，除了计算最大公约数，还求解了方程 ax + by = gcd(a, b) 的整数解。在上述示例中，x = 1，y = -2 是方程的一个整数解，可以通过对 x 和 y 的乘法因子进行调整获得其他整数解。