本篇博客是【数论专题】系列的第 \(7\) 篇，希望大家多多支持。
若 \(a\times x\equiv 1\pmod p\)，并且 \(a, p\) 互质，则称 \(a\) 模 \(p\) 的乘法逆元为 \(x\)，记作 \(a^{-1}\)。
费马小定理求逆元
注意，当模数 \(p\) 是质数且 \(a\ne 0\) 时，才可使用费马小定理求逆元。
根据费马小定理：
\[a^{p - 1}\equiv 1\pmod p
\]
因此：
\[a\times a^{p - 2}\equiv 1\pmod p\\
\]
很明显，此时 \(a^{p - 2}\) 即为 \(a^{-1}\)。
使用快速幂求出 \(a^{p - 2}\bmod\ p\) 即可，时间复杂度 \(O(\log p)\)。
int qpow(int a, int b, int mod)
{int ans = 1;while(b){if(b & 1) ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;
}//快速幂模板
int get_inv(int a, int p)
{return qpow(a, p - 2, p);//求出逆元
}
扩展欧几里得算法求逆元
\(a\times x\equiv 1 \pmod p\) 可以转化为求解 \(a\times x + p\times y = \gcd(a, p) = 1\)（当 \(\gcd(a, p) = 1\) 才有解，这也符合逆元的定义）。那么，可以使用扩展欧几里得算法求解。
但是，求解出来的 \(x\) 可能是负数，需要通过累加 \(p\) 来处理一下。
void exgcd(int a, int b)//扩展欧几里得算法模板
{if(b == 0){x = 1, y = 0;return;}exgcd(b, a % b);int tmp = x;x = y;y = tmp - a / b * y;
}
int get_inv(int a, int p)
{exgcd(a, p);return (x % p + p) % p;//使 x 变为最小正整数解
}
递推求逆元
设 \(p = k\times i + r, r < i, 1 < i < p\)，然后把这个式子放在 \(\bmod\ p\) 意义下可以得到：
\[k\times i + r \equiv 0\pmod p
\]
将两边同时乘上 \(i^{-1}\) 和 \(r^{-1}\) 可以得到：
\[\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ k\times r^{-1} + i^{-1}\equiv 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \pmod p\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i^{-1}\equiv -k\times r ^ {-1}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \pmod p\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i^{-1}\equiv - \lfloor \frac{p}{i} \rfloor \times (p\bmod\ i)^{-1}\pmod p
\]
通过这个式子即可从前面的数推出当前数的逆元。
void get_inv(int n, int p)
{inv[1] = 1;//初始值for(int i = 2;i <= n;i ++) inv[i] = (p - p / i) * inv[p % i] % p;//递推式
}