各种求逆元

标签：数学方法——数论

阅读体验：

版权声明：部分知识采集于书本《数学一本通》（定义呀什么的）

费马小定理

当\(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\)模板题：

线性递推求逆元

这个直接背下来吧，我不太会证明

感性理解一下：\[inv[i]=(p-p/i)*inv[p\%i])\%p\]上网百度证明去吧

突然发现这篇好短啊

那又怎么样。。。咧咧咧