book
归档: OI 
flag
mode_edit

作用

在$O(n)$时间内求出$1-n$在$\text{mod}\ p$意义下的所有逆元

原理

可以递推求出,比如我们现在要求$i$在$\text{mod}\ p$意义下的逆元

我们知道

$$
p = ki+r\ (r < i)
$$

然后我们对这个式子进行一发操作

$$
ki + r \equiv 0\ \text{mod}\ p
$$

突然想起来我们是要求逆元,即$i^{-1}$,那我们就瞎搞一下,搞出来个$\frac{1}{i}$就好了

$$
\because ki+r=0\
\therefore ki=-r \
对上面的式子两边取倒数得
\therefore -\frac{1}{ki}=\frac{1}{r}\
\therefore i^{-1}=-\frac{k}{r}
$$

$i^{-1}$就是我们想要的东西啦

然后再考虑一下怎么算$k,r$。

显然$k=\lfloor\frac{p}{i}\rfloor$,$r=p\ \text{mod}\ i$。又因为$r<i$ ,你又是大力递推的,所以$inv[r]$一定已经计算过了,所以直接用就好了。

代码

int inv[(int)3e6 + 10], n, p;
void get_inv()
{
    inv[1] = 1;
    for (int i = 2; i <= n; ++i)
        inv[i] = (1ll * inv[p % i] * (p - p / i) % p) % p;
}
navigate_before navigate_next