問題引入

如何求 \(\dfrac{a}{b}\)？小學數學告訴我們，\(\dfrac{a}{b} = a \times \dfrac{1}{b}\)。

那么若 \(a, b, p \in \mathrm{\mathbf{Z}}\)，如何求 \(\dfrac{a}{b} \bmod \ p\)，并且 \(a\) 和 \(b\) 都是八常大數？就像剛才我們把 \(a\) 乘上 \(b\) 的倒數一樣，這里我們也需要用到 \(b\) 的“倒數”，不過是 \(\bmod \ p\) 意義上的倒數，我們稱之為 “乘法逆元”。

定義與性質

如果有 \(ax \equiv 1 \pmod p\)，我們就稱 \(x\) 是 \(a\) 在 \(\bmod \ p\) 意義下的乘法逆元。

既然說乘法逆元是一種“倒數”，自然擁有以下性質：

記 \(x\) 是 \(a\) 在 \(\bmod \ p\) 意義下的乘法逆元，則有

求法

求單個數的逆元：擴展歐幾里得定理

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

得到的 \(x\) 就是 \(a\) 在模 \(b\) 意義下的乘法逆元。注意：我們求得的 \(x\) 可能不是最小的解，為了使解最小，可以對 \(b\) 取模。

求從 \(1\) 到 \(n\) 每個數的逆元

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

擴展應用：組合數取模

考慮組合數公式 \(C_n^m = \dfrac{n!}{m!(n-m)!}\)。\(n! \bmod \ p\) 很好說，但是如何計算階乘倒數取模？

有以下公式：

其中 \(\mathrm{invfac}(x)\) 指 \(x\) 的階乘逆元。

因此大數組合數取模代碼如下：

fact[0] = infact[0] = 1;
for (int i = 1; i <= x; i++) {
  fact[i] = fact[i-1] * i % MOD;
  infact[i] = infact[i-1] * quickPow(i, MOD-2) % MOD;
}
ll getC(int a, int b) {
  return fact[a] * infact[a-b] % MOD * infact[b] % MOD;
}