c语言EXGCD求乘法逆元

在数学中，如果a和n是整数，且它们互质，那么a对于模n的乘法逆元是一个整数x，满足ax ≡ 1 (mod n)。在C语言中，可以使用扩展欧几里得算法（EXGCD）来求解乘法逆元。EXGCD可以求出最大公约数以及满足等式mx+ny=gcd(m,n)的一组(x,y)。如果a和n互质，那么ax+ny=1，其中x就是a对于模n的乘法逆元。因此，我们可以使用EXGCD来求解a对于模n的乘法逆元。

具体实现方法如下：
1. 定义一个函数exgcd，输入参数为a、b、x、y，输出参数为最大公约数gcd和满足等式mx+ny=gcd(m,n)的一组(x,y)。
2. 在函数中，首先判断b是否为0，如果为0，则返回a作为最大公约数，同时将x赋值为1，y赋值为0。
3. 如果b不为0，则递归调用exgcd函数，输入参数为b、a%b、y、x-a/b*y，输出参数为gcd和一组(x,y)。
4. 最后返回gcd作为a对于模b的乘法逆元。

下面是C语言代码实现：

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int gcd = exgcd(b, a % b, y, x - a / b * y);
    return gcd;
}

int mod_inverse(int a, int n) {
    int x, y;
    int gcd = exgcd(a, n, x, y);
    if (gcd != 1) {
        // a和n不互质，不存在乘法逆元
        return -1;
    } else {
        // 返回a对于模n的乘法逆元
        return (x % n + n) % n;
    }
}