[学习笔记]逆元

2024-03-12 09:00:32

逆元

1.定义

　　乘法逆元是一个可以用来进行除法求余的手段,若\(ax\equiv1(mod\;p)\),则称x为a在mod p意义下的逆元。记为\(a^{-1}\)。于是我们可以简易的得到在mod p意义下，a的逆元就是它的倒数，于是除就变成了乘，就可以取余了。

注意可以有逆元的前提是\(a\perp p\)（互质）

2.求解逆元

1）扩展欧几里得求解乘法逆元

由上述可得，逆元满足如下式子
\[ ax+py=1 \]
看见这个式子我们就可以很显而易见的想到Exgcd求解。代码如下

void Exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) x=1,y=0;
    else Exgcd(b,a%b,y,x),y-=a/b*x;
}
int NY(int a,int p){
    ll x,y;
    Exgcd(a,p,x,y);
    return (x%p+p)%p;
}

2）费马小定理求解乘法逆元

由费马小定理可知\(a^{p-1}\equiv1(mod\;p)\)于是我们可以将式子变形为\(a*a^{p-2}\equiv1(mod\;p)\),所以说在modp意义下\(a^{p-2}\)就是a的逆元，我们使用快速幂求解，此处不给出代码。

3）递推求解乘法逆元

对于多个连续的乘法逆元来说，是可以用递推来求解的。

对于求1~n中的mod p意义下的逆元，首先我们保证n<p（此处暂不解释原因）。对于一个单独的i，我们想要求解\(i^{-1}\)，于是我们令\(p=ki+r(0<=r<i)\)，于是得到\(ki+r\equiv0(mod\;p)\)，等式两边同时乘上\(i^{-1},r^{-1}\)，得到\(kr^{-1}+i^{-1}\equiv0(mod\;p)\)，移项可得\(i^{-1}\equiv -\lfloor{p/i}\rfloor*(p\;mod\;i)^{-1}(mod\;p)\),于是我们便得到一个可行的逆元，记\(inv[i]\)为i的逆元，可得递推式：
\[ inv[i]=-(p/i)*inv[p\%i]; \]
但是在具体实现中我们常常为了保证逆元不是一个负数或者防止一些其他的错误，我们写成：
\[ inv[i]=((p-p/i)*inv[p\%i]+p)\%p; \]
注意：此处我们保证n<p，是因为逆元要求互质！！！

3.例题

[SDOI2008]沙拉公主的困惑

题解链接

码农公寓

逆元