乘法逆元

        乘法逆元在ACM中常用于在除法运算取模，这是一个重要方法。
        首先先认识什么是乘法逆元，对于整数a，若存在整数x使得$ax\equiv1(mod p)$，则称x为a关于1模p的乘法逆元。
        将同余式化为整除式可得$ax+py=1$，根据裴蜀定理可知a与p互质，即$gcd(a,p)=1$。这说明当且仅当a与p互质时，a关于模p的乘法逆元才存在。

        乘法逆元有什么作用呢？它常用于除法的取模，已知：

$$(a+b)\ mod\ p=(a\ mod\ p+b\ mod\ p)\ mod\ p\\ (a-b)\ mod\ p=(a\ mod\ p-b\ mod\ p)\ mod\ p\\ ab\ mod\ p=(a\ mod\ p)(b\ mod\ p)\ mod\ p$$

        但是除法并没有：

$$\frac a b\ mod\ p=\frac {a\ mod\ p} {b\ mod\ p}\ mod\ p$$

        这对计算除法的模带来困难，乘法逆元可以解决这个问题，假设最后结果为x，则有：

$$\frac a b\equiv x(mod\ p)$$

        当b与p互质时，上式等价于：

$$a\equiv bx(mod\ p)$$

        设b的乘法逆元为b^-1，即有：

$$bb^{-1}\equiv 1(mod\ p)$$

        那么有：

$$ab^{-1}\equiv b^{-1}bx\equiv x(mod\ p)$$

        所以如果要算a/b对p的模，只需计算ab^-1对p的模即可，关键在于求b的逆元。下面先介绍两种通用方法。

• 用费马小定理求解逆元

【费马(Fermat)小定理】当p为质数且a与p互质时，有$a^{p-1}\equiv 1(mod p)$

        费马小定理变形一下得到$aa^{p-2}\equiv 1(mod p)$，那么逆元就是a^p-2。用快速幂算法求出a^p-2并取模就是逆元。这个方法需要p为质数，并且a与p互质。
        费马小定理其实是欧拉定理的特殊情况，p不为质数时，用欧拉函数值代替p-1然后求逆元也是可以的，这样便不要求p为质数。

• 用扩展欧几里得算法求解逆元

        当a与p互质时，可以用扩展欧几里得算法求出一个特解x、y使得$ax+bp=1$，也就是$ax\equiv 1(mod p)$，这样x就是逆元。本方法只需要a与p互质（这也是逆元存在的条件），缺点是求出的x可能为负数。

---

        若用inv(x)来表示x的乘法逆元，则有：

$$inv(ab)\equiv inv(a)inv(b)(mod\ p)$$

        这说明逆元是积性的，很容易证明，这是逆元的一个重要性质。
        最后介绍逆元的递推求法。对于一个数a，现欲求a在模p意义下的逆元，根据带余除法原理，可以将p表示为ak+b。假设b的逆元为b^-1，那么：

$$bb^{-1}\equiv 1(mod\ p)$$

        也就是：

$$(p-ak)b^{-1}\equiv 1(mod\ p)$$

        即：

$$pb^{-1}-akb^{-1}\equiv -akb^{-1}\equiv 1(mod\ p)$$

        因此：

$$-kb^{-1}\equiv a^{-1}(mod\ p)$$

        就得到了一个递推式：

$$inv(a)\equiv -(p/a)inv(p\ mod\ a)(mod\ p)$$

        这个递推式可以帮助我们在O(n)复杂度下求出1~n的逆元。