最近打的幾場比賽,都出現了有關逆元的題目,今天就整理了一下...
求乘法逆元的幾種方法:http://www.cnblogs.com/james47/p/3871782.html
博文轉載連結:http://blog.csdn.net/acdreamers/article/details/8220787
今天我們來探讨逆元在ACM-ICPC競賽中的應用，逆元是一個很重要的概念，必須學會使用它。
對于正整數和，如果有，那麼把這個同餘方程中的最小正整數解叫做模的逆元。
逆元一般用擴充歐幾裡得算法來求得，如果為素數，那麼還可以根據費馬小定理得到逆元為。
推導過程如下
求現在來看一個逆元最常見問題，求如下表達式的值（已知）
當然這個經典的問題有很多方法，最常見的就是擴充歐幾裡得，如果是素數，還可以用費馬小定理。
但是你會發現費馬小定理和擴充歐幾裡得算法求逆元是有局限性的，它們都會要求與互素。實際上我們還有一
種通用的求逆元方法，适合所有情況。公式如下
現在我們來證明它，已知，證明步驟如下