数论分块

本质就是利用取整分数值的块状分布。

UVA11526 H(n)

题意： 求 ${\sum }_{i=1}^n\frac{n}{i}$。

解析：

$\lfloor \frac{n}{i}\rfloor$ 只有 $O(\sqrt{n})$ 种取值，考虑将相同值同时处理。时间复杂度 $O(T\sqrt{n})$。

对于 $i$，其块右端点 $j$ 满足：$j=\lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor }\rfloor$。

证明：对所有 $\lfloor \frac{n}{i}\rfloor =k$ 的 $i$：由 $k\le \frac{n}{i}$，有 $\lfloor \frac{n}{k}\rfloor \ge \lfloor \frac{n}{\frac{n}{i}}\rfloor =\lfloor i\rfloor =i$。

故 $\lfloor \frac{n}{k}\rfloor$ 即 $\lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor }\rfloor$ 即为该块所在右端点。

代码

[AHOI2005] 约数研究

考虑约数 $i$ 在 $1\sim n$ 中出现次数，即 $i$ 的倍数个数，为 $\frac{n}{i}$。答案即为 ${\sum }_{i=1}^n\lfloor \frac{n}{i}\rfloor$。

时间复杂度 $O(\sqrt{n})$。

代码

约数和

同样考虑约数的贡献，即求 ${\sum }_{i=1}^{n}i\times \lfloor \frac{n}{i}\rfloor$。

考虑到原式子 $<{\sum }_{i=1}^{n}n$，long long 即可。

时间复杂度 $O(\sqrt{n})$。

代码

[CQOI2007] 余数求和

$$\begin{gathered} \sum _{i=1}^{n}k\mathrm{mod}i \\ =\sum _{i=1}^n(k-\lfloor \frac{k}{i}\rfloor i) \\ =nk-\sum _{i=1}^n\lfloor \frac{k}{i}\rfloor i \end{gathered}$$

枚举到 $k$ 即可，$n,k$ 同阶时时间复杂度 $O(\sqrt{n})$。

CF1485C Floor and Mod

妙。

法一：

$$\lfloor \frac{a}{b}\rfloor =a\mathrm{mod}b$$

$$\lfloor \frac{a}{b}\rfloor =a-\lfloor \frac{a}{b}\rfloor b$$

$$\lfloor \frac{a}{b}\rfloor =\frac{a}{b+1}$$

有 $b+1\mid a$。

由 $\lfloor \frac{a}{b}\rfloor <b$，得 $a<b^2+b$。

而 $b+1\mid a$，由 $a<b^2+b$，得 $b\nmid a$，故 $\lfloor \frac{a}{b}\rfloor =\frac{a}{b+1}$。

综上，$b+1\mid a$ 且 $a<b^2+b$ 是原命题的一个充要条件。

答案即为
$$\sum _{b=1}^y\frac{\min (x,b^2+b-1)}{b+1}$$。

分段整除分块即可。

总结：根据整除关系、范围得到一些性质，从而找出充要条件。

代码

法二（官方做法）

记 $\lfloor \frac{a}{b}\rfloor =a\mathrm{mod}b=k$。

$$a=kb+k$$

$$b+1=\frac{a}{k}$$

由 $k<b$，得 $k+1<\frac{a}{k}$，故 $k$ 为根号级别。

枚举 $k$，考虑 $b$ 的数量。可得 $b\le \frac{x}{k}-1$，且 $k<b\le y$。

总结：观察 + 放缩 $k$ 的范围。

代码