Loading...

乘法逆元 学习&&复习笔记

check评论:1 条 remove_red_eye浏览量:577 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-28

定义:如果$a\times x \equiv 1 \pmod b$,且满足$a$与$b$互质,则称$x$是在模$b$意义下$a$的逆元

求逆元一般可以用来做有理数取模,比如问你$\frac{a}{b}\bmod 19260817$,就可以把式子化成$a\times b^{-1} \bmod 19260817$

因为$b^{-1}\times b \equiv 1\pmod {19260817}$,所以$b^{-1}$是$b$的逆元,我们将$a$与$b$的逆元相乘再取模即可

求逆元的几种方法:

$1.$快速幂

我们观察一下费马小定理,如果$p$是质数并且$gcd(a,p)=1$,那么$a^{p-1}\equiv 1 \pmod p$

把后面的式子拆开,得到$a\times a^{p-2}\equiv 1\pmod p$

所以$a^{p-2}$就是$a$的逆元啦qwq

我们用快速幂处理就好

$2.$扩展欧几里得$(exgcd)$

对于这个式子$a\times x\equiv 1 \pmod p$,我们将其转化成不定方程$ax+py=1$,我们直接用$exgcd$求出$x,y$的一组解即可

$3.$递推式

令$p=ki+r$,$k=\lfloor \frac{p}{i}\rfloor,r=p\bmod i$,$(i < p,k<p,r<i)$

则有$ki+r\equiv 0\pmod p$

左右同乘$i^{-1}\times r^{-1}$,得$k\times r^{-1}+i^{-1}\equiv 0\pmod p$

即$i^{-1}\equiv (-k)\times r^{-1}\pmod p$

带入$k$的值,得到

$i^{-1}= (-\lfloor\frac{p}{i}\rfloor)\times(p\bmod i)^{-1} \pmod p$

由于$(p \bmod i)<i$,所以我们在求出$i$的逆元之前已经得到了$(p\bmod i)$的逆元

用$inv$数组记录$i$的逆元,得到$inv[i]=(-\frac{p}{i})\times inv[p\bmod i]\bmod p$

因为我们要保证$i$的逆元大于$0$,故把答案加上$p$之后再取模

即$inv[i]=p+(-\frac{p}{i})\times inv[p\bmod i]\bmod p$

初始值$inv[0]=0,inv[1]=1$

就差不多了qwq

仅有一条评论

正在回复给  
去登陆?

   点击刷新验证码

    Decoration
    2018 - 10 - 28 10 : 37

    qwq

标签云

文章留名