乘法逆元

定义

如果一个线性同余方程
\(ax \equiv 1 \pmod b\)，
则 \(x\) 称为 \(a \bmod b\) 的逆元，记作 \(a^{-1}。\)

求法：

扩展欧几里得法

void exgcd(int a, int b, int& x, int& y) {
  if (b == 0) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
}

前置知识

线性同余方程

定义

形如

\(ax\equiv b\pmod n\)
的方程称为 线性同余方程（Linear Congruence Equation）。其中，$a、b $和 \(n\) 为给定整数，\(x\) 为未知数。需要从区间 \([0, n-1]\) 中求解 \(x\)，当解不唯一时需要求出全体解。

线性求逆元

求出 \(1,2,\dots,n\) 中每个数关于 p 的逆元。

如果对于每个数进行单次求解，以上两种方法就显得慢了，很有可能超时，所以下面来讲一下如何线性\(（O(n)）\)求逆元。

首先，很显然的 \(1^{-1} \equiv 1 \pmod p；\)
对于 \(\forall p \in \mathbf{Z}，有 1 \times 1 \equiv 1 \pmod p\) 恒成立，故在 p 下 1 的逆元是 1，而这是推算出其他情况的基础。

实现

inv[1] = 1;
for (int i = 2; i <= n; ++i) {
  inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}