前提了解：

=其实是三个横线，同余打不出来
欧拉定理：当a,p互质 a^(f(p))=1(mod p)  f(x)是欧拉函数
下面的费马小定理其实就是欧拉定理的特殊情况，当p为质数，f(p)=p-1，带入即得费马小定理

费马小定理：
如果p为质数，a^p=a(mdo p)  
如果p为质数，且a不是p的整数倍，则a^(p-1)=1（mod p）


为什么要求逆元，什么情况下要用逆元？
答：除法没有取模公式，可以转化为乘法取模

逆元：
a/b=a*x(mod p)

逆元存在的充要条件：

b与p互质，即gcd(b,p)=1;

当p为质数

a/b=a*x(mod p)          x为b模p的乘法逆元
a/b*b=a*b*x(mod p)
a    =a*b*x(mod p)
1    =b*x  (mod p)
b*x  =1  (mod p)
当p是质数时，可以用费马小定理，得
b^(p-1)=1(mdo p)
b*b^(p-2)=1(mod p)
即逆元x=b^(p-2)             //即b的模m的逆元是b^(p-2)
因为该证明用到了费马小定理，因此只有当b为质数时才可以用快速幂求逆元。
当b是p的倍数时，b*x=0(mod p)此时逆元无解即此时逆元不存在
因为p是质数，此时b与p不互质可以写成b%p==0
因此当p是质数，且b不是p的倍数时，可以用快速幂求解

当p不是质数时

当p不是质数，我们就不可以用上述证明用到的费马小定理了，此时也就不可以用快速幂求逆元了，
那么我们该如何求呢？
若x为b模p的乘法逆元
有1/b=x(mod p)
有1=b*x(mod p)
即x*b=1(mod p)
有x*b+tp=1;   //因为b,p互质，即gcd(b,p)=1，即x*b+tp=gcd(b,p);联系裴蜀定理，可使用扩展欧几里得算法求解。
求出来的b的系数即为b的模p的逆元
因此此时可以用扩展欧几里得算法求逆元

注：参考大佬https://www.acwing.com/solution/content/3054/