ExtGcd
在數論和演算法競賽中，我們經常需要在模運算 (Modular Arithmetic) 的環境下進行除法。然而，模運算中沒有直接的除法操作。取而代之的是，我們需要找到一個數的「模乘法反元素」，並將除法轉換為乘法。 本文將介紹什麼是模乘法反元素，以及如何使用擴展歐幾里得算法 (Extended Euclidean Algorithm, ExtGcd) 來高效地找到它。 什麼是模乘法反元素？ 對於兩個整數 a 和 m，如果存在一個整數 x 滿足以下同餘方程式： a * x ≡ 1 (mod m) 那麼，我們稱 x 是 a 在模 m 下的模乘法反元素 (Modular Multiplicative Inverse)。 有了反元素 x，當我們想計算 b / a (mod m) 時，就可以轉換為計算 b * x (mod m)，從而實現模運算中的「除法」。 反元素的存在條件 並不是所有的 a 在模 m 下都有反元素。反元素存在的充分必要條件是 a 和 m 互質 (coprime)，也就是說它們的最大公因數 (Greatest Common Divisor, GCD) 為 1。 gcd(a, m) = 1 如果 gcd(a, m) ≠ 1，那麼 a 在模 m 下的乘法反元素不存在。 ...