題目傳送門

如何求 \(x\ (x>1)\) 在模 \(p\) 意義下的逆元：

1. 做帶余除法：設 \(p=kx+r\ (r<x)\)，其中 \(k=\lfloor\dfrac{p}{x}\rfloor,\ r=p\bmod x\)，顯然有 \(k<p\)
   則 \(kx+r=p\equiv 0 \pmod p\)

2. 反解 \(x\)，得 \(x\equiv -rk^{-1}\pmod p\)

3. 兩邊取倒數，得 \(x^{-1}\equiv -kr^{-1}\pmod p\)

注意 \(-k < 0\)，不能直接乘，而由 \(-k\equiv p-k\pmod p\)，所以我們可以用 \(p-k\) 替換 \(k\)。

這樣我們就得到了 \(x\) 的逆元：\(x^{-1}\equiv (p-k)r^{-1}\pmod p\)，其中 \(k=\lfloor\dfrac{p}{x}\rfloor,\ r=p\bmod x\)

由于 \(r<x\)，所以在從小到大遞推 \(x^{-1}\) 的時候，\(r^{-1}\) 肯定已經計算過了。

補一個 \(1^{-1}\equiv 1\pmod p\)

以上。