数论分块

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

UVA11526 H(n)

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

解析：

$\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$。

代码

约数和

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

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

代码

[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}$$

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$。

由 $\frac{a}{b+1}=a\mathrm{mod}b<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$ 的范围。

代码

[清华集训2012] 模积和

推式子：

式子是比较容易推的。

$$\sum _{i=1}^n\sum _{j=1}^m(n\mathrm{mod}i)\times (m\mathrm{mod}j),i\ne j$$

$$\sum _{i=1}^n\sum _{j=1}^m(n-\lfloor \frac{n}{i}\rfloor i)\times (m-\lfloor \frac{m}{j}\rfloor j)\text{\hspace{1em}(1)}$$
$$\sum _{i=1}^{\min (n,m)}(n-\lfloor \frac{n}{i}\rfloor i)\times (m-\lfloor \frac{m}{i}\rfloor j)\text{\hspace{1em}(2)}$$

答案为 $(1)-(2)$。

$(1):$

$$\sum _{i=1}^n\sum _{j=1}^m(n-\lfloor \frac{n}{i}\rfloor i)\times (m-\lfloor \frac{m}{j}\rfloor j)$$

$$=\sum _{i=1}^n\left((n-\lfloor \frac{n}{i}\rfloor i)\sum _{j=1}^m(m-\lfloor \frac{m}{j}\rfloor j)\right)$$

$$=\sum _{i=1}^n(n-\lfloor \frac{n}{i}\rfloor i)\times \sum _{j=1}^m(m-\lfloor \frac{m}{j}\rfloor j)$$

显然可以分别拿出来数论分块，时间复杂度 $O(\sqrt{n})$。

$(2):$

$$\sum _{i=1}^{\min (n,m)}(n-\lfloor \frac{n}{i}\rfloor i)\times (m-\lfloor \frac{m}{i}\rfloor i)$$

$$=\sum _{i=1}^{\min (n,m)}(nm-m\lfloor \frac{n}{i}\rfloor i-n\lfloor \frac{m}{i}\rfloor i+\lfloor \frac{n}{i}\rfloor \lfloor \frac{m}{i}\rfloor i^2)$$

对于前三项的计算是比较容易的，考虑第四项：

无非整除分块的块多了一点，考虑块内两者值均相等，此时 $i$ 所在块右端点为 $\min (\lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor }\rfloor ,\lfloor \frac{m}{\lfloor \frac{m}{i}\rfloor }\rfloor )$。

对于平方和，${\sum }_{i=1}^n{i}^2=\frac{n(n+1)(2n+1)}{6}$。证明可以考虑归纳证明，或者构造一个三次多项式证明。

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

实现：

考虑到乘法操作会爆 long long，可以取模用逆元或者 __int128。

需注意 19940417 不是质数。

代码

[ARC068E] Snuke Line

对于每个 $d$，$[l_i,r_i]$ 内 $d$ 的倍数个数为 $\lfloor \frac{r_i}{d}\rfloor -\lfloor \frac{l_i-1}{d}\rfloor$，即求 ${\sum }_{i=1}^n[\lfloor \frac{r_i}{d}\rfloor -\lfloor \frac{l_i-1}{d}\rfloor >0]$。

对于每个 $i$，对所有的 $d$ 做数论分块，对每个块做区间加操作，单点查询，考虑差分。

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

考虑到 $d\in [l_i,r_i]$ 一定可行，加上这个剪枝即可通过本题。代码