各种求逆元

数学方法——数论
阅读体验：https://zybuluo.com/Junlier/note/1300025
版权声明：部分知识采集于书本《数学一本通》（定义呀什么的）

费马小定理

当$p$为质数时，$x$的逆元为$x^{p-2}\mod p$
当然不可能这么简单便宜了你
所以有限制：只有p为质数时才可以用

扩展欧几里德$Exgcd$

$Exgcd$本来是用来求 $ax+by=gcd(a,b)$ 的一组特解的
由于逆元的定义：
若$a*x \equiv1(\mod b)$ ，那么$x$为$a$的逆元
这个式子又可以转化成：$ax+by=1$ 。。。
这就是$exgcd$可以做的辣(很显然$a,b$互质的)
那么再放一个$Exgcd$的板子（总打错。。。）

lst Exgcd(lst a,lst b,lst &x,lst &y)
{
    if(!b){x=1,y=0;return a;}
    lst ss=Exgcd(b,a%b,x,y),t;
    t=x,x=y,y=t-a/b*y;
    return ss;
}
//直接背板子然后直接用，返回的值ss是a和b的GCD
//反正特解在x里面了就行了。。。一些题目也可以好好运用这个GCD。。。

$Exgcd$模板题：luoguP1082 [Noip2012]同余方程

线性递推求逆元

这个直接背下来吧，我不太会证明
感性理解一下：

突然发现这篇好短啊
那又怎么样。。。咧咧咧