$x$ 满足 $a\cdot x \equiv 1 \pmod{m} $ ; $x$ 称之为 $a$ 对模 $m$ 的逆，记作 $a^{-1}$
性质
- 若 $\gcd(a, m) = 1$ $\iff$ $a$ 在模 $m$ 下有逆元
逆元的求解
扩展欧几里得算法
设 $a\cdot x + m\cdot y = 1$
$a\cdot x = 1-m\cdot y \equiv 1 \pmod m$
$x$ 是 $a$ 对 $m$ 的逆元，问题转化为求方程 $a\cdot x + m\cdot y = 1$ 的正整数解
$\gcd(a,m) = 1$ 方程必有解，扩展欧几里得算法跑一下方程，求出 $x$ 再模 $p$ 处理
复杂度 $\mathcal{O}(\log_2^n)$
1int exgcd(int a, int b, int &x, int &y)
2{
3 if(!b) { x = 1; y = 0; return a; }
4 int g = exgcd(b, a%b, y, x);
5 y -= a/b*x;
6 return g;
7}
费马小定理
$\tau(p)=2,\ \gcd(a,p) =1 \implies a^{p-1}\equiv 1 \pmod p$
$a*a^{p-2} \equiv 1\pmod p,\ a$ 在模 $p$ 下的逆元为 $a^{p-2}$
快速幂求 $a^{p-2}$ 即可
复杂度 $\mathcal{O}(\log_2^n)$
1int qp(int a, int b, int p) //qp = quick power
2{
3 if(!b) return 1;
4 if(b&1) return a*qp(a*a%p, b>>1, p)%p;
5 else return qp(a*a%p, b>>1, p)%p;
6}
7int ie = qp(a, p-2, p); //ie = inverse element
Fermat-Euler 定理
$\gcd(a,m) = 1$ 时 $a^{\varphi(m)} \equiv 1 \pmod m$
所以 $a^{\varphi(m)-1}$ 是 $a$ 在模 $m$ 下的逆元
需要求 $\varphi(m)$，再用快速幂求 $a^{\varphi(m)-1}$
不推荐
线性递推
求 $\forall{a},a\in[1,p-1]$ ，模 $p$ 的逆元
令 $ax + b = p;\ b\cdot b^{-1} \equiv 1 \pmod p$
$\because b = p-ax$
$\therefore (p-ax)\cdot b^{-1} \equiv 1 \pmod p \implies a\cdot(-x\cdot b^{-1}) \equiv 1 \pmod p$
$\therefore a^{-1}\equiv (-x\cdot b^{-1}) \equiv (p-x)\cdot b^{-1} \pmod p$
$a > b$ 直接动态规划扫一遍就好了
在计算机中 $b$ 表示为 p%a，$x$ 表示为 p/a
复杂度 $\mathcal{O}(n)$
1int inv[p] = {0, 1}; //inv = inverse element
2for(int i = 2; i < p; i++){
3 inv[i] = (p-p/i) * inv[p%i] % p;
4}