乘法逆元

乘法逆元是數學中的一個概念，指的是對於給定的數a和模數m，存在另一個數b，使得a乘以b的積除以m的餘數為1，即\(a \times b \equiv 1 \pmod{m}\)。在這種情況下，b稱為a關於模m的乘法逆元。

乘法逆元的一個重要套用是在模運算中，當需要進行除法運算時，由於不能直接將兩個數除以第三個數，可以通過乘法逆元將除法轉換為乘法。例如，在模m運算中，如果需要計算\(c = \frac{a}{b} \pmod{m}\)，可以找到b的乘法逆元\(b^{-1}\)，然後計算\(c = a \times b^{-1} \pmod{m}\)，這樣就可以避免直接的除法運算。

求乘法逆元的方法包括擴展歐幾里得算法、費馬小定理加快速冪、以及線性求逆元法等。其中，擴展歐幾里得算法可以同時找到最大公約度和乘法逆元；費馬小定理適用於當模數為質數p時，a的乘法逆元為\(a^{p-2} \pmod{p}\)；線性求逆元法則是一種預處理技巧，可以在O(n)的時間內計算出多個逆元。