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

文章目录

• 线性推逆元的递推式
• 原理与证明
• 代码
• 参考

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

答案是肯定的。

线性推逆元的递推式

（模数是 $N$，$\lfloor x \rfloor$ 表示 $x$ 向下取整）

$$inv(i)=(N-N/i)\ast inv(N\bmod i)\bmod N$$

原理与证明

在某位大佬的博客上看到一个证明。（以下 $a/b$ 与 $\displaystyle \lfloor \frac a b \rfloor$ 均表示 $a$ 整除 $b$ ）

假设 $\displaystyle k=\lfloor \frac N i \rfloor ,b=N \bmod i$；显然有：

$$k \ast i + b \equiv 0 \pmod N$$

变换得到：

$$-k \ast i \equiv b \pmod N$$

两边同除 $i \ast k$：

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

把 $k$ 和 $b$ 换回来，就得到了！

$$

• \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)$ 有很多个，我们可以求出最小的一个，一定小于等于 $N$（证明详见：乘法逆元的三种求法），所以左边的 $\bmod N$ 可以去掉了。右边有个 $\bmod N$ ，为了让右边大于 0，我们可以给它加上 $N$。

$$inv(i) = (N-N/i) \ast inv(N \bmod i) \bmod N$$

初始 $inv(0)=1$，可以愉快地递推啦～

代码

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

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

参考

逆元详解 - CSDN博客