辗转相除法求函数逆元

辗转相除法求函数逆元是一种常用的方法。通过辗转相除法可以求出一个数的逆元，即使这个数和模数不互质。这种方法通常用于求解线性方程和求解欧拉定理中的逆元。

在C语言中，可以使用下述代码实现辗转相除法求函数逆元：

// 求逆元 a，m
int Inv_a(int a, int m) {
    int x, y;
    int d = exgcd(a, m, x, y);
    if (d == 1) {
        return (x % m + m) % m; // 保证逆元为正数
    } else {
        return -1; // ax + my = 1 不成立，即 a，m 不互质，无解
    }
}

其中，`exgcd`是扩展欧几里德算法，用于求解线性方程ax + my = 1中的解。

通过调用`Inv_a`函数，可以得到给定数a在模m下的逆元。