各种求逆元

标签：数学方法——数论
阅读体验：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;}
	rg lst ss=Exgcd(b,a%b,y,x);
	y-=a/b*x;return ss;
}
//直接背板子然后直接用，返回的值ss是a和b的GCD
//反正特解在x里面了就行了。。。一些题目也可以好好运用这个GCD。。。

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

线性递推求逆元

这个直接背下来吧，我不太会证明
感性理解一下：$$inv[i]=(p-p/i)*inv[p%i])%p$$~~上网百度证明去吧~~

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