「杂谈」逆元

问题：求 \(a^{-1} \bmod m\)，其中 \((a, m) = 1\)，\(m > 1\)。

快速幂

当 \(m\) 是质数时，由费马小定理，\(a^{m - 1} \equiv 1 \pmod m\)，因此 \(a^{m - 2} \equiv a^{-1} \pmod m\)。

EXGCD

解方程 \(ax + my = (a, m) = 1\)，则 \(a^{-1} \equiv x \pmod m\)。

多项式牛顿迭代

当 \(m = 2^k\) 时，把 \(a\) 看成一个 \(\mathbb{Z}_2\) 上的多项式 \(A(x)\)，求 \(A(x)^{-1} \bmod x^k\) 并代入 \(2\) 即可。

实现（求 \(a^{-1} \bmod 2^{32}\)）：

ui inv(ui a) {
  ui b = 1;
  for (int i = 0; i < 5; ++i) b *= 2 - a * b;
  return b;
}