目录
逆元的概念：
逆元的用处：
逆元的四种求法：
快速幂求逆元
扩展欧几里得求逆元
欧拉函数求逆元
线性递推求逆元：
逆元是什么？有什么作用？怎么求逆元呢？
逆元的概念：
如果 a * x1 (mod p) 成立，那么 x 是 a 在 mod m 的条件下的逆元注意，a和x一定都和p互质，如果不互质，则逆元不存在逆元的用处：
计算a / b(mod p) 的值时，如果 b 是一个很大的数，那么会爆double的精度；假设除数 b 的逆元为 inv[b] ，那么可做如下转换
a / b (mod p)a * inv[b]( mod p)
把除法转变成了乘法，避免的精度的损失；为什么上述式子是等价的呢？
设 b* k = 1 (mod p) 则 k 就是 b 的逆元（即k = inv[b]） ；所以 b = (m * p +1) / k ，那么 a / b = a /( (m * p +1)/k)mod p = a * k/(m * p + 1)mod p=a * k(mod p)
如此妙哉~
逆元的四种求法：
快速幂求逆元
快速幂求逆元的前提是费马小定理的成立：
费马小定理
在模数p为素数的前提下，1 (mod p)
将费马小定理变形一下 ——》* a1 (mod p)
由此可得，a的逆元就是(mod p)
所以，用快速幂求出的结果就行了；
扩展欧几里得求逆元
传送门：扩展欧几里得
由 a * x1(mod p) 得 a*x = y0 * p +1 令y=-y0, b = p;
推出：ax + by = 1（注意：前提gcd(a,b) == 1）
然后用扩欧解方程即可，得出来的 x 就是 a 在mod p 意义下的逆元
欧拉函数求逆元
传送门：欧拉函数
欧拉定理：若 a 和 p 互素 ，设Φ(p) 为小于p且与p互素的正整数的个数，则有
则 ：* a
得出就是 a 在mod p 意义下的逆元
线性递推求逆元：
递推公式：
inv[1] = 1inv[i] = (p-p/i) * inv[p%i] % p(i>=2开始递推)
