c语言线性同余法算法

线性同余方程在C语言中通常用于解决模运算的问题，比如找到两个大数之间的互逆元，或者求解模意义下的方程。下面是一个简单的C语言函数，展示了如何通过迭代法计算两个整数a和m (m > 0) 的模反元素x，即满足ax ≡ 1 (mod m)。

#include <stdio.h>

// 线性同余法求解ax ≡ 1 (mod m)
int extended_euclidean_algorithm(int a, int m, int *x, int *y) {
    if (m == 0) {
        *x = 1;
        *y = 0;
        return a; // 如果m=0，则a就是所求的模反元
    } else {
        int x1, y1;
        int gcd = extended_euclidean_algorithm(m, a % m, &x1, &y1);
        *x = y1;
        *y = x1 - (a / m) * y1; // 计算x值
        return gcd;
    }
}

int main() {
    int a, m, x, y;
    printf("Enter the value of a and m: ");
    scanf("%d %d", &a, &m);

    if (gcd(a, m) == 1) { // 检查是否互质
        extended_euclidean_algorithm(a, m, &x, &y); // 计算模反元
        printf("The modular inverse of %d modulo %d is: %d\n", a, m, x);
    } else {
        printf("Numbers are not coprime.\n");
    }

    return 0;
}

在这个例子中，`extended_euclidean_algorithm`函数利用了递归和欧几里得算法来计算最大公约数和模反元素。用户输入a和m，程序会判断它们是否互质（如果最大公约数为1），然后计算并显示模反元。