SkyWT / 博客 / 以 O(N) 线性时间复杂度递推逆元的方法

以 O(N) 线性时间复杂度递推逆元的方法

2018 年 8 月 9 日 06:54


文章目录

在之前我们已经知道乘法逆元的三种求法,对于一般的题目让你把答案模一个质数,如果要求逆元一般用费马小定理,可以在 Θ(Nlog2(N))\Theta (Nlog_2(N)) 时间内构造出 1 到 N 的逆元:inv(x)=xmo2modmoinv(x)=x^{mo-2} \bmod mo。但是对于 10710^7 级别的 NN,这样的求法就显得有点慢。能不能在 Θ(N)\Theta (N) 时间内递推出 inv(x)inv(x) 呢?

答案是肯定的。

线性推逆元的递推式

(模数是 NNx\lfloor x \rfloor 表示 xx 向下取整)

inv(i)=(NN/i)inv(Nmodi)modNinv(i)=(N-N/i)\ast inv(N\bmod i)\bmod N

原理与证明

某位大佬的博客上看到一个证明。(以下 a/ba/bab\displaystyle \lfloor \frac a b \rfloor 均表示 aa 整除 bb

假设 k=Ni,b=Nmodi\displaystyle k=\lfloor \frac N i \rfloor ,b=N \bmod i;显然有:

ki+b0(modN)k \ast i + b \equiv 0 \pmod N

变换得到:

kib(modN)-k \ast i \equiv b \pmod N

两边同除 iki \ast k

kinv(b)inv(i)(modN)-k \ast inv(b) \equiv inv(i) \pmod N

kkbb 换回来,就得到了!

$$

  • \lfloor \frac N i \rfloor \ast inv(N \bmod i)\equiv inv(i) \pmod N \
    inv(i) \bmod N = - (N/i) \ast inv(N \bmod i) \bmod N \
    $$

因为 inv(i)inv(i) 有很多个,我们可以求出最小的一个,一定小于等于 NN(证明详见:乘法逆元的三种求法),所以左边的 modN\bmod N 可以去掉了。右边有个 modN\bmod N ,为了让右边大于 0,我们可以给它加上 NN

inv(i)=(NN/i)inv(Nmodi)modNinv(i) = (N-N/i) \ast inv(N \bmod i) \bmod N

初始 inv(0)=1inv(0)=1,可以愉快地递推啦~

代码

其实知道了递推式,代码就两行……

    inv[0]=1;
    for (int i=1;i<=M;i++) inv[i]=(N-(N/i))*inv[N%i]%N;

参考

逆元详解 - CSDN博客


暂无评论


发表新的评论

所有评论都将经过博主审核。请勿填写无意义邮箱或发表无关评论、广告等,否则会被视为垃圾评论。

提交评论即表明你同意本网站使用 Cookie,并允许本站在后台记录你的邮箱、IP 地址等必要信息。这些信息不会被透露给其他用户。(提交一次评论后,本提示将不再展示)