线性时间递推 $0\sim p-1$ 在模 $p$ 意义下的乘法逆元。

首先 $1^{-1}\equiv 1\pmod p$。

设 $p=k\ast i+r\left(1\le r \lt i\lt p\right)$。

所以有 $k\ast i+r\equiv 0\pmod p$。

两边同乘以 $r^{-1}$、$i^{-1}$，有 $i^{-1}\equiv -k\ast r^{-1}\pmod p$。

即 $i^{-1}\equiv -\lfloor \frac pi\rfloor\ast (p\ \text{mod}\ i)^{-1}\pmod p$

洛谷p3811

const int MAXP=3e6+5;
int inv[MAXP];
void get_inv(int p){
	inv[1]=1;
	_for(i,2,p)
	inv[i]=1LL*(p-p/i)*inv[p%i]%p;
}

数论分块用于解决形如 $\sum_{i=1}^n \lfloor \frac ni\rfloor$ 的问题，时间复杂度 $O(\sqrt n)$。

由于部分 $\lfloor \frac ni\rfloor$ 的值相同，所以考虑分块计算。

设对 $\forall i \in\lfloor l, r\rfloor$，有 $\lfloor \frac ni\rfloor$ 的值相同。

显然 $l$ 等于上一个块的 $r$ 加 $1$，故只需要考虑 $r$ 的计算。

事实上有 \begin{equation}\lfloor \frac n{\lfloor \frac nl\rfloor}\rfloor\le \frac n{\lfloor \frac nl\rfloor}\lt \lfloor \frac n{\lfloor \frac nl\rfloor}\rfloor+1\end{equation}

移项，得 \begin{equation}\frac n{\lfloor \frac n{\lfloor \frac nl\rfloor}\rfloor+1}\lt\lfloor \frac nl\rfloor\le \frac n{\lfloor \frac n{\lfloor \frac nl\rfloor}\rfloor}\end{equation}

所以有 \begin{equation}r=\lfloor \frac n{\lfloor \frac nl\rfloor}\rfloor\end{equation}

关于算法的时间复杂度分析，有时间复杂度等于 $\lfloor \frac ni\rfloor$ 的可能取值个数。

当 $\lfloor \frac ni\rfloor \le \sqrt n$ 时，显然这样的取值不超过 $\sqrt n$ 个。

当 $\lfloor \frac ni\rfloor \gt \sqrt n$ 时，有 $i \lt \sqrt n$，所以这样的取值也不超过 $\sqrt n$ 个。

综上所述，$\lfloor \frac ni\rfloor$ 的可能取值个数只有 $O(\sqrt n)$ 个，时间复杂度证毕。

洛谷p2261