乘法逆元是数论中重要的内容，也是 ACM 中常用到的数论算法之一。所以，如何高效的求出乘法逆元是一个值得研究的问题。 这里我们只讨论当模数为素数的情况，因为如果模数不为素数，则不一定每个数都有逆元。

定义

在  mod p的意义下我们把 $x$ 的乘法逆元写作 x ^ {-1}x​−1​​。
乘法逆元有如下的性质：
乘法逆元的一大应用是模意义下的除法，除法在模意义下并不是封闭的，但我们可以根据上述公式，将其转化为乘法。

费马小定理

要求 $p$ 为素数。 上述公式可变形为 由乘法逆元的定义，a ^ {p - 2}a​p−2​​ 即为 $a$ 的乘法逆元。 使用快速幂计算 a ^ {p - 2}a​p−2​​，总时间复杂度为 $O(\log a)$。

代码

inline int pow(const int n, const int k) { long long ans = 1; for (long long num = n, t = k; t; num = num * num % MOD, t >>= 1) if (t & 1) ans = ans * num % MOD; return ans; } inline int inv(const int num) { return pow(num, MOD - 2); }

扩展欧几里得

扩展欧几里得（EXGCD）算法可以在 $O(\log \max (a,b))$ 的时间内求出关于 $x$、$y$ 的方程
的一组整数解 当 $b$ 为素数时，$\gcd (a,b)=1$，此时有 时间复杂度为 $O(\log a)$。

代码

void exgcd(const int a, const int b, int &g, int &x, int &y) { if (!b) g = a, x = 1, y = 0; else exgcd(b, a % b, g, y, x), y -= x * (a / b); } inline int inv(const int num) { int g, x, y; exgcd(num, MOD, g, x, y); return ((x % MOD) + MOD) % MOD; }

递推法

代码

inv[1] = 1; for (int i = 2; i <= MAXN; i++) inv[i] = ((-(MOD / i) * inv[MOD % i]) % MOD + MOD) % MOD;
下面是ACdreamers关于递推求解逆元的推导过程（个人觉得他的更好）
其实有些题需要用到模的所有逆元，这里为奇质数。那么如果用快速幂求时间复杂度为， 如果对于一个1000000级别的素数，这样做的时间复杂度是很高了。实际上有的算法，有一个递推式如下                         它的推导过程如下，设，那么             对上式两边同时除，进一步得到             再把和替换掉，最终得到             初始化，这样就可以通过递推法求出模奇素数的所有逆元了。   另外模的所有逆元值对应中所有的数，比如，那么对应的逆元是。