完整題本 PDF：中文、英文、馬來文。

在初等數學中，我們學過實數的聯立方程式。假設有這樣一個聯立方程式：
$$
\left\{
\begin{array}{ccc}
A_{1, 1} x_1 + A_{1, 2} x_2 + \dots + A_{1, n} x_n & = & b_1 \\
A_{2, 1} x_1 + A_{2, 2} x_2 + \dots + A_{2, n} x_n & = & b_2 \\
\vdots & = & \vdots \\
A_{n, 1} x_1 + A_{n, 2} x_2 + \dots + A_{n, n} x_n & = & b_n
\end{array}
\right.
$$

這個著名的問題可以用高斯消去法來解決。該方法的概念相當簡單。我們對增廣矩陣 $[A|b]$ 應用基本行運算，即將一行的倍數加到另一行。可以證明，在這個運算之後，$Ax = b$ 的解不會受到影響。
然後，為了消去第 $n$ 項，我們查看第 $2$ 到第 $n$ 個方程，對於第 $i$ 個方程，我們找到係數 $c = -\frac{A_{i, n}}{A_{1, n}}$，並讓新的第 $i$ 行為：
$$(cA_{1, 1} + A_{i, 1})x_1 + (cA_{1, 2} + A_{i, 2})x_2 + \dots (cA_{1, n-1} + A_{i, n-1})x_{n-1} + (cA_{1, n} + A_{i, n})x_n = cb_1 + b_i$$
由於 $cA_{1, n} = -A_{i, n}$，實際上是：
$$(cA_{1, 1} + A_{i, 1})x_1 + (cA_{1, 2} + A_{i, 2})x_2 + \dots (cA_{1, n-1} + A_{i, n-1})x_{n-1} + 0x_n = cb_1 + b_i$$
因此第 $n$ 項在第 $i$ 個方程中被消去了。

類似地，這個過程可以套用在第 $n-1$ 項上。利用新產生的第二個等式，可以消去第三個到最後一個等式中的第 $n-1$ 項。重複進行這個消去 $n-1$ 次，會得到新的 $A'$ 和 $b'$，並且，滿足 $i > j$ 的 $A'{i, j}$ 都一定會是零。特別地，第 $n$ 個方程式會變成簡單的 $A'{n, 1}x_1 = b'_n$。在已知 $x_1$ 之後，第 $(n-1)$ 個方程式也只會剩下一個未知數 $x_2$。接著，再從第 $n$ 個方程式開始，回頭依序代入每一個等式到第一個為止，即可依序解出所有 $x$。整個過程僅需 $O(n ^ 3)$ 次運算即可完成。

這個方法直接且易於理解。然而，由於使用了除法，我們實際上無法在模運算的世界中使用這個方法來求解。但，我們真的不能嗎？

事實上，雖然除法通常在模運算的世界中不能直覺的使用，但我們可以用某種方式來定義除法。當我們思考除法的定義 $\frac{a}{b} = x$ 時，它實際上是找到 $x$ 使得 $x \times b = a$。有了這個想法，在模運算的世界中，我們也可以嘗試找到 $x$ 使得 $x \times b \equiv a \pmod{m}$。為了做到這一點，我們必須利用費馬小定理。

費馬小定理指出，對於質數 $p$ 和任何整數 $a, (1 \leq a < p)$，$a ^ p \equiv a \pmod{p}$。有了這個，我們也知道 $a ^ {p-1} \equiv 1 \pmod{p}$。現在，為了找到 $x$ 使得 $x \times b \equiv a \pmod{p}$，我們可以證明 $x = a \times b ^ {p-2} \pmod{p}$ 是一個有效的解。

剩下要解決的最後一個問題是如何計算 $b ^ {p-2} \pmod{p}$。天真地進行計算需要 $O(p)$ 時間，這太慢了（在這個問題中，$m$ 可以大到 $10 ^ 9$！）。不過這可以用快速冪的技巧來完成。

這個技巧適用於任何帶有整數指數的一般指數計算。為了計算 $a ^ b$，我們可以計算
$a ^ 0, a ^ 1, a ^ 2, a ^ 4, a ^ 8, \dots, a ^ {2 ^ k}$，其中 $k = \lfloor \log_2 b \rfloor$。然後，由於我們可以將 $b$ 分解為 2 的冪次和，我們可以通過乘以適當的 $a$ 的冪來計算 $a ^ b$。這可以在 $O(\log b)$ 時間內完成。將模運算應用於這個技巧不會改變複雜度。因此，我們可以在 $O(n ^ 3 \log m)$ 時間內解決聯立方程式問題。現在，你能解決它嗎？