用c++写extended Euclid算法求s，t

Extended Euclidean Algorithm (欧几里得扩展算法)是一种求解两个整数最大公约数（Greatest Common Divisor, GCD）及其余数的算法，并且同时可以找到一组系数x和y，使得ax + by = gcd(a, b)，这里a和b是给定的整数，而s和t就是对应的系数。

在C++中，你可以用以下步骤编写这个算法：

#include <iostream>

// 定义函数用于计算GCD和Bézout's coefficients
int extendedEuclid(int a, int b, int& s, int& t) {
    if (b == 0) {
        s = 1; // 当b为0时，s=1，因为gcd(a, 0) = a
        t = 0; // t=0，表示x=0
        return a;
    } else {
        int x, y; // 存储中间结果
        int d = extendedEuclid(b, a % b, x, y); // 递归调用
        s = y; // 更新s，等于原来x的值
        t = x - (a / b) * y; // 更新t，等于原来的x减去商乘以新的y
        return d;
    }
}

int main() {
    int a, b, s, t;
    std::cout << "Enter two numbers: ";
    std::cin >> a >> b;

    // 调用函数并存储结果
    int gcd_value = extendedEuclid(a, b, s, t);

    std::cout << "GCD of " << a << " and " << b << " is: " << gcd_value << "\n";
    std::cout << "Coefficients for Bezout's identity: s=" << s << ", t=" << t << "\n";

    return 0;
}

当你运行这个程序，它会提示用户输入两个数字，然后计算它们的最大公约数以及满足ax + by = gcd(a, b)的系数s和t。