数论分块小结

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16531978.html

概念

下面除法皆表示整除

求：

$\sum_{i=1}^n \frac n i$

显然，暴力 $O(n)$ ，但有很多结果是相同的，所以可以分段每一段分别处理，大概有 $\sqrt n$ 段

令这一段的左端点（最小值）为 $l$ ，设 $k=\dfrac n l$ ，我们要找一个最大值 $r$ 满足 $\dfrac n r=k$ ，显然 $r=\dfrac n{\frac n l}$ ，则 $[l,r]$ 的和为 $\dfrac n l\times (r-l+1)$

数论分块

下面除法默认下取整

$\Large G(n, k)\\\Large = \sum_{i = 1}^n k \bmod i\\\Large=\sum_{i=1}^n(k-\frac k i\times i)\\\Large=n\times k-\sum_{i=1}^ni\times\frac k i$

显然，对于 $\frac k i$ 必然是很多段连续的数组成，所以可以分块处理，也就是数论分块。

设当前这一块左端点为 $l$ ，结果为 $a=\dfrac k l$ ，则 $r=\dfrac k l=\dfrac k {\frac k l}$ ，前面乘 $i$ 可以直接套等差数列求和公式。

时间复杂度 $O(\sqrt k)$

以下分数皆表示整除

$\Large\max(n\bmod i)\\\Large=\max(n-\frac n i\times i)\\\Large=n+\max(-\frac n i\times i)\\\Large=n-\min(\frac n i \times i)$

显然，当 $\frac n i$ 一定时， $i$ 越小越好，所以可以把每个 $\frac n i$ 求出来，然后数列分块取最小值即可

显然， $f(x)$ 就是 $x$ 的因数个数。

设 $S(n)=\sum_{i=1}^nf(i)$ ，所以答案在求 $S(r)-S(l-1)$

对于任意 $i\in[1,n]$ ，它作为小于等于 $n$ 的数的约数个数为 $\dfrac n i$ （向下取整），于是 $S(n)=\sum_{i=1}^n \dfrac n i$

观察上式， $S(n)$ 显然可以通过数论分块在 $O(\sqrt n)$ 的时间求出。

总时间复杂度 $O(\sqrt r)$

显然数论分块

然后统计一下每一块内1到9出现的情况乘上 $n/l$ 即可

设 $n\leq m$

$\Large\sum_{i=1}^{n} (n \bmod i) \times \sum_{j=1}^{m}(m \bmod j)-\sum_{i=1}^ n (n\bmod i)(m\bmod i)$

前面那两坨就是个数论分块板子，后面那块拆一下：

$\Large \sum_{i=1}^n(nm-\frac m i\times in-\frac n i \times im+\frac m i\times\frac n i\times i^2)$

这里还是可以数论分块，每次块的 $r$ 可以取 $\min(\dfrac m l, \dfrac n l)$

然后还有几个难点