模逆运算算法思路以及用c语言实现思路

模逆运算算法是指在模运算下，求解一个数的乘法逆元，即找到一个数与原数相乘后模一个数等于1。其算法思路可以使用扩展欧几里得算法来实现，具体步骤如下：

1. 根据模数m和原数a，使用扩展欧几里得算法求出最大公约数gcd和x、y的值，即：gcd(a, m) = ax + my；
2. 如果gcd不等于1，则无法求出逆元，返回错误；
3. 否则，根据扩展欧几里得算法的结果，有ax + my = 1，将其两边同时模m，得到ax ≡ 1 (mod m)；
4. 因此，x就是a在模m下的乘法逆元。

以下是用C语言实现模逆运算算法的代码：

int mod_inverse(int a, int m) {
    int gcd = 0, x = 0, y = 0;
    int flag = extended_euclidean(a, m, &gcd, &x, &y);
    if (flag == -1) { // gcd不等于1
        return -1;
    } else {
        return (x % m + m) % m; // 返回a在模m下的乘法逆元
    }
}

int extended_euclidean(int a, int b, int *gcd, int *x, int *y) {
    if (b == 0) {
        *gcd = a;
        *x = 1;
        *y = 0;
        return 0;
    } else {
        int flag = extended_euclidean(b, a % b, gcd, x, y);
        int temp = *x;
        *x = *y;
        *y = temp - (a / b) * (*y);
        return flag;
    }
}

其中，extended_euclidean函数是扩展欧几里得算法的实现，返回值为-1表示gcd不等于1，否则返回0。mod_inverse函数则是调用了extended_euclidean函数，返回a在模m下的乘法逆元。