最近打的几场比赛,都出现了有关逆元的题目,今天就整理了一下...
求乘法逆元的几种方法:http://www.cnblogs.com/james47/p/3871782.html
博文转载链接:http://blog.csdn.net/acdreamers/article/details/8220787
今天我们来探讨逆元在ACM-ICPC竞赛中的应用，逆元是一个很重要的概念，必须学会使用它。
对于正整数
和
，如果有
，那么把这个同余方程中
的最小正整数解叫做模的逆元。
逆元一般用扩展欧几里得算法来求得，如果为素数，那么还可以根据费马小定理得到逆元为
。
推导过程如下
求现在来看一个逆元最常见问题，求如下表达式的值（已知
）
当然这个经典的问题有很多方法，最常见的就是扩展欧几里得，如果是素数，还可以用费马小定理。
但是你会发现费马小定理和扩展欧几里得算法求逆元是有局限性的，它们都会要求与互素。实际上我们还有一
种通用的求逆元方法，适合所有情况。公式如下
现在我们来证明它，已知，证明步骤如下
