复习之路：关于逆元，我们首先知道一个叫做“完全剩余系”的东西，记为Zn,即mod n剩下的数；还有一个叫做 “缩系”的东西，就是Zn中与n互质的元素，记为Zn*；那么在Zn中，若ab = 1 ，那么a的逆就是b，b的逆就是a，类似于倒数，只不过这些都是mod n剩下的；而要说的乘法逆元的定义就如上所示。我们要求乘法逆元有两种方式，首先介绍三个定理：1、之前讲到的乘法逆元，即ax = 1 (mod p),根据EXGCD我们知道要求gcd(a, p) = 1;2、费马小定理：    如果说a是整数，p是质数，那么a^p - a = k * p(p的倍数);即 a^p = a (mod p)；    如果说a不是p的倍数那么我们有a^(p-1) = 1（mod p）因为若果a是p的倍数该等式是不成立的3、扩展欧几里得（EXGCD），详情见：一、根据如上定理我们来看为什么可以用费马小定理来求解乘法逆元：前提：p是质数，且a不是p的倍数证明: 由前提可知 a^p-1 = 1(mod p)；即a * a ^ (p-2) = 1 (mod p);        那么我们可以知道a的乘法逆元就是a^(p-2) 使用快速幂计算即可，quick_pow详见：
二、利用扩欧：前提：无证明：要求乘法逆元，即ax = 1 (mod p)可以推出： ax - py = 1；x是a的乘法逆元 带入扩欧求解即可，最后判断逆元有无的条件就是 gcd(a, p) 是否为1.这是因为：    ax + by 的最小解应该是gcd(a, b)；如果gcd(a, b) 不为1 的话，就不是乘法逆元的二元一次方程式了；根据扩欧求解乘法逆元模板：int solve(ll a,ll p) { ll d, x, y; exgcd(a, p, d, x, y); return d == 1 ? (x + p) % p : -1; }
PS:逆元的作用： 做题时如果结果过大一般都会让你模一个数，确保结果不是很大，而这个数一般是1e9+7，而且这个数又是个素数，加减乘与模运算的顺序交换不会影响结果，但是除法不行。有的题目要求结果mod一个大质数，如果原本的结果中有除法，比如除以a,那就可以乘以a的逆元替代。（除一个数等于乘它的倒数，虽然这里的逆元不完全是倒数，但可以这么理解，毕竟乘法逆元就是倒数的扩展）。