START
为什么需要求逆元？
显然对于加减乘运算都会满足：
(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)，这个可以通过举例验证一下或者可以通过(b%p)可以为0但是分母不能为0得到对于除法而言不满足这个运算的结论。
但是如果非要求(a/b)%p要怎么办呢？
这个时候就用到了逆元。
设b的逆元x，再设(b*x)=1 (mod p)
首先证明这个x就是b相对于p的逆元：我们对(a/b)上下同时乘x，则(a*x/(b*x))%p=a*x%p(分母为1)，这个x就是b相对于p的逆元，注意这个说法，是b相对于p的逆元，单纯说某个数的逆元是没有意义的，只有说某个数相对于某个模数的逆元才有意义。
接下来是怎么求逆元：
求逆元依据的式子是（b*x）=1 (mod p)
求逆元有两种方法：
1.运用费马小定理：a^(p-1) =1 (mod p)，a,p互质
式子左边a^(p-1)=a*a^(p-2)，那么有a*a^(p-2)=1 (mod p)
对比b*x = 1 (mod p)，显然x=b^(p-2)，接下来直接快速幂就行了
2.运用扩欧
我们将(b*x) = 1 (mod p)，改写成b*x+k*p=1。
对于b*x+k*p=1 (一般k<0)这个式子，我们知道(b*x+k*p)%p=1。
对比扩欧的a'x'+b'y'=gcd(a,b)。
得到：a'=b,x'=x,b'=p,gcd(a,b)=1。
通过exgcd(b,p,x,y)可以求出逆元x。
END