c++扩展欧几里得算法代码

以下是使用C++实现的扩展欧几里得算法的示例代码：

#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 = 56;
    int b = 15;
    int x, y;
    int gcd = extendedGCD(a, b, x, y);

    std::cout << "GCD(" << a << ", " << b << ") = " << gcd << std::endl;
    std::cout << "贝祖等式: " << gcd << " = " << x << "*" << a << " + " << y << "*" << b << std::endl;

    return 0;
}

运行此代码，将输出：

GCD(56, 15) = 1
贝祖等式: 1 = -4*56 + 15*15

这个例子演示了如何使用扩展欧几里得算法计算56和15的最大公约数，并输出它们的贝祖等式。