分别用python和C语言写出扩展欧几里得算法

扩展欧几里得算法，也称为中国剩余定理的逆元版本，用于求解一组线性同余方程组的最大公约数及其系数。以下是Python和C语言的实现：

**Python:**

def extended_euclidean(a, b):
    if b == 0:
        return (a, 1, 0)
    else:
        d, x, y = extended_euclidean(b, a % b)
        return (d, y, x - (a // b) * y)

# 使用示例
a = 45
b = 63
gcd, x, y = extended_euclidean(a, b)
print(f"最大公约数(GCD): {gcd}")
print(f"x: {x}, y: {y} 可以满足 ax + by = gcd")

**C语言:**

#include <stdio.h>

// 定义递归函数计算最大公约数和系数
int extended_euclid(int a, int b, int *x, int *y) {
    if (b == 0) {
        *x = a;
        *y = 1;
        return a;
    }
    int gcd = extended_euclid(b, a % b, y, x);
    *y -= a / b * (*x);
    return gcd;
}

// 主函数测试
void test() {
    int a = 45;
    int b = 63;
    int x, y;
    int gcd = extended_euclid(a, b, &x, &y);
    printf("最大公约数(GCD): %d\n", gcd);
    printf("x: %d, y: %d 满足 ax + by = gcd\n", x, y);
}

int main() {
    test();
    return 0;
}

在这个例子中，`extended_euclid` 函数会返回两个整数 `x` 和 `y`，它们满足 `ax + by = gcd`。你可以根据需要调用这个函数并存储结果。