扩展欧几里得算法c语言

扩展欧几里得算法，也称为中国剩余定理的一种特殊情况，它是用于求解两个整数的最大公约数（GCD）以及一组线性同余方程组的解的算法。在C语言中，你可以通过迭代的方式实现这个算法，通常它包括以下几个步骤：

1. **基础步骤**：首先计算a和b（一般假设a > b）的大约最大公约数（如果它们相等，则直接返回），然后找到m和n使得a * m + b * n = gcd(a, b)。

2. **递归查找**：如果b != 0，那么继续应用扩展欧几里得算法到新的整数对(b, a % b)，并保存中间结果。

3. **存储解决方案**：在每次递归中，同时记录下新的m值，因为这将是我们需要的同余方程的解。

下面是一个简单的C语言函数示例，展示了如何实现扩展欧几里得算法：

#include <stdio.h>

// 定义扩展欧几里德算法
int extended_euclidean(int a, int b, int *x, int *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    int x1, y1;
    int gcd = extended_euclidean(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
    return gcd;
}

int main() {
    int a, b, x, y;
    printf("Enter two numbers to find their GCD and linear combination: ");
    scanf("%d%d", &a, &b);

    // 获取最大公约数和线性系数
    extended_euclidean(a, b, &x, &y);

    printf("The GCD of %d and %d is %d.\n", a, b, x);
    printf("The solution for the linear equation ax + by = gcd(a, b) is x = %d, y = %d.\n", x, y);

    return 0;
}