【OI之路】11更高级数论-2逆元

逆元(严格来说叫乘法逆元)

除法与模

这个东西我们之前稍微讲了一下哈:
【OI之路】02数论算法-1公约数公倍数与欧几里得

补充一些内容:

$ (a+b)\mod p=(a\mod p)+(b\mod p)\mod p (对) $
$ (a-b)\mod p=(a\mod p)-(b\mod p)\mod p (对) $
$ (a\times b)\mod p=(a\mod p)\times (b\mod p) \mod p (对) $
$ \frac{a}{b}\mod p=\frac{a\mod p}{b\mod p}\mod p (错) $
$ a^b\mod p=(a^{b-k}\mod p)\times (a^{k}\mod p)\mod p (对) $
没错,除法中是错误的【随便举个反例即可,毕竟“证明对的难,证明错的容易”】
那容易爆的可以搞快速幂,但碰到有模数的时候,难道就不用除法了?
当然不是,所以,有请逆元隆重登场!

啥玩意?

$a\times x=1 (\mod p)$
是不是有点像数学里面的倒数?只不过这里因为是数论,所有是整数
现在x就叫做mod p下a的逆元
可见p不同,a的逆元也不同。

用法?

可以把除以a变成乘以a的逆元(始终强调模意义下)
爽吧~
然后koi的时候就半懂不懂地杠最后一题,讲题的时候全程懵逼

求法1

欧拉-费马定理
条件:gcd(a,p)=1 【原本就是定理的条件】
因为费马小定理还额外要求p是素数 【亲自实验验证】
所以不定模数或者已知是合数的时候线性筛好欧拉函数
$a^{\varphi(p)}=1 (\mod p)$
$inv(a)=a^{-1}=a^{\varphi(p)-1} (\mod p)$

求法2

扩展欧几里德算法~
就问你6不6
条件:gcd(a,p)=1 【扩展欧几里德要求K(这里的1)是gcd(A,B)的倍数】
$a\times x+p\times y=1$
$a\times x\%p+p\times y\%p=1\%p$
$a\times x\%p=1\%p$
$x=inv(a) (\mod p)$
复杂度O(loga)
记得取最小正整数解哟

求法3

当p是个质数的时候有
$inv(a)=(p-\lfloor p/a \rfloor)\times inv(p\%a)\%p$

证明:
设$x=p\%a,y=\lfloor p/a \rfloor 【a<p】$
于是有$y\times a+x=p$ 【就是整数除法定义嘛】
$y\times a+x=0 (\mod p)$
$x=(-y)\times a (\mod p)$
$inv(a)=(p-y)\times inv(x) (\mod p)$
$inv(a)=(p-\lfloor p/a \rfloor)\times inv(p\%a) (\mod p)$

边界:$inv(1)=1$
时间复杂度:单个O(loga),但加上记忆化可以线性

总结

条件:gcd(a,p)=1
这个条件不是由求法而得来的(例如第三种就不需要),而是由其定义
$a \times inv(a)=1 (\mod p)$
那么exBSGS算法中说过
对于一个同余方程组,左边、右边和模数会有相同的质因子(除非是0)
而现在右边是1,则$gcd(a \times inv(a),p)=1$
则$gcd(a,p)=1$

单个复杂度:O(loga)
预处理:线性

练习

Tag-逆元

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/71d2.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%