乘法逆元作用

先说一下什么叫做逆元：
逆元
数论倒数，又称逆元

数论中的倒数是有特别的意义滴

你以为a的倒数在数论中还是1/a吗

(・∀・)哼哼~天真

先来引入求余概念

(a + b) % p = (a%p + b%p) %p （对）

(a - b) % p = (a%p - b%p) %p （对）

(a * b) % p = (a%p * b%p) %p （对）

(a / b) % p = (a%p / b%p) %p （错）

为什么除法错的

证明是对的难，证明错的只要举一个反例

(100/50)%20 = 2 ≠ (100%20) / (50%20) %20 = 0

对于一些题目，我们必须在中间过程中进行求余，否则数字太大，电脑存不下，那如果这个算式中出现除法，我们是不是对这个算式就无法计算了呢？

答案当然是 NO (>o<)

这时就需要逆元了

我们知道

如果

a*x = 1

那么x是a的倒数，x = 1/a

但是a如果不是1，那么x就是小数

那数论中，大部分情况都有求余，所以现在问题变了

a*x = 1 (mod p)

那么x一定等于1/a吗

不一定

所以这时候，我们就把x看成a的倒数，只不过加了一个求余条件，所以x叫做 a关于p的逆元

比如2 * 3 % 5 = 1，那么3就是2关于5的逆元，或者说2和3关于5互为逆元

总结起来就是

设c是b的逆元，则有b*c≡1(mod m)；
推论：(a/b)mod m = (a/b)1mod m = (a/b)bc mod
m=ac(mod m); 即a/b的模等于a * (b的逆元)的模；
这个推论也就说明了为什么要引入逆元；

逆元的作用
一句话就是，将除法改为乘法；

例如 求 (A / B) %p ；在B的值非常大的情况下，B作为除数，极有可能会爆精度；除数不能太大；所以我们可以把他转化为乘法来解决；

(a/b)mod m = (a/b)*1mod m = (a/b)bc mod
m=ac(mod m);
即a/b的模等于a * (b的逆元)的模；
所以按照这个推论求这个式子的步骤就明了了；

求出B的逆元 （扩展欧几里得，费马小引理+快速幂）都可以求出；
引用公式推论套用即可；