逆元

2019-04-14 17:17发布

站内文章 / 模拟电子
15880 0 1216

逆元

什么是逆元？ 对于整数a，若ax=1(mod p)，则称x为a模p意义下的逆元
逆元有什么用？ 一般地，逆元用来实现取模下的除法 对我们知道a*(1/a)=1，在模p意义下a*x mod p=1，所以x可以看做是模p意义下的1/a

逆元的求法

1、扩展欧几里得算法

ax=1(mod p)可以化为ax-py=1，可以用扩展欧几里得算法求出x

2、费马小定理

根据费马小定理，对于质数p有：a^(p-1)=1(mod p) 则有a*a^(p-2)=1(mod p) 所以a^(p-2)=1/a(mod p)
所以我们用快速幂就可以在O(logp)时间求出逆元=a^(p-2) mod p

3、递推公式

如果要用到很多数的逆元，一个个求就显得有些浪费时间，这里有一个O(n)求出n以内所有数逆元的方法： 记inv[i]为i的逆元，则 inv[i]=(p-p/i)*inv[p%i]%p 我们可以线性筛出，也可以O(logp)递归求单逆元

热门文章