数论分块学习笔记

---

学了半天的莫比乌斯反演，结果只听懂了数论分块 = =

综述

对于含有 $\lfloor\frac{n}{i}\rfloor$ 的求和式子，可以通过合并一些相等的 $\lfloor\frac{n}{i}\rfloor$，从而在 $O(\sqrt{n})$ 的时间里算出式子的值

引入

考虑计算

$$\sum_{d = 1}^{n} \left\lfloor\frac{n}{d}\right\rfloor$$

可以发现，$\lfloor\frac{n}{d}\rfloor$ 会出现相同的值，$O(n)$ 的做法慢就慢在对于相同的 $\lfloor\frac{n}{d}\rfloor$ 计算了多次…

如果能知道每个取值对应 $n$ 的区间以及相应 $\lfloor\frac{n}{d}\rfloor$ 的值，就可以在优于 $O(n)$ 的时间里计算 $\sum_{d = 1}^{n} \lfloor\frac{n}{d}\rfloor$

对于正整数 $n$，当 $1\leq d\leq n$ 时，$\lfloor\frac{n}{d}\rfloor$ 的不同的取值个数不超过 $2\sqrt{n}$，证明如下

若 $1 \leq d \leq \sqrt{n}$，$\lfloor\frac{n}{d}\rfloor$ 取值不超过 $\sqrt{n}$ 种

若 $\sqrt{n} < d \leq n$，有 $\lfloor\frac{n}{d}\rfloor \leq \frac{n}{d} < \sqrt{n}$，$\lfloor\frac{n}{d}\rfloor$ 取值也不超过 $\sqrt{n}$ 种

因此，使用数论分块计算的复杂度为 $O(\sqrt{n})$

接下来要确定这段取值相同区间的左右端点，也就是说

对于任意一个 $L$，求最大的 $R$，满足 $\lfloor\frac{n}{L}\rfloor = \lfloor\frac{n}{R}\rfloor$，其中 $R = \left\lfloor\frac{n}{\lfloor\frac{n}{L}\rfloor}\right\rfloor$，证明如下

由 $\lfloor\frac{n}{L}\rfloor \leq \frac{n}{L}$，可得

$$\left\lfloor\frac{n}{\lfloor\frac{n}{L}\rfloor}\right\rfloor \geq \left\lfloor\frac{n}{\frac{n}{L}}\right\rfloor = \lfloor L\rfloor = L$$

故 $R = \left\lfloor\frac{n}{\lfloor\frac{n}{L}\rfloor}\right\rfloor$，此时 $R$ 为最大值

例题

洛谷 P2261 [CQOI2007]余数求和

求

$$\sum_{i = 1}^{n}k \bmod i$$

其中 $n,\;k\leq10^9$ 且为正整数

• 由 $O(1)$ 快速乘的经验，实际上是模运算的定义，原式可化为

$$\sum_{i = 1}^{n} \left(k - \left\lfloor\frac{k}{i}\right\rfloor \cdot i\right)$$

即

$$n\cdot k - \sum_{i=1}^{n} \left\lfloor\frac{k}{i}\right\rfloor \cdot i$$

$\lfloor\frac{k}{i}\rfloor$ 就数论分块了，$\sum_{i=1}^{n}i$ 可以等差数列求和

不过这道题有一处坑点 = =

考虑到 C++ 中，除以或模 0 就会 RE，因此需要特判 k/L == 0 的情况。那么，什么时候 $\lfloor\frac{k}{L}\rfloor = 0$ 呢，那肯定是 $\lfloor\frac{k}{L}\rfloor$ 的最后取值了，故 $R$ 取 $n$

G = n*k;
for (int L = 1, R; L <= n; L = R+1) {
    if (k/L) R = min(k / (k/L), n);
    else R = n;
    G -= (k/L) * (L+R)*(R-L+1)/2;
}

洛谷 P2260 [清华集训2012]模积和

求

$$\sum_{i=1}^{n}\sum_{j=1}^{m}(n \bmod i)\cdot(m\bmod j),\;i \neq j$$

结果 $\bmod\; 19940417$ 的值。其中 $n,\;m\leq10^9$ 且为正整数

和上一题相似的思路，考虑将模运算置换为取整。不过在这一步前，要先把 $i\neq j$ 的条件干掉

$$\sum_{i=1}^n(n\bmod i) \cdot \sum_{i=1}^m(m\bmod i) - \sum_{i=1}^{\min(n, m)}(n \bmod i)\cdot(m\bmod j)$$

不妨设 $n\leq m$，这样写起来更简单一点

$$\left(n^2 - \sum_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor \cdot i\right)\cdot \left(m^2 - \sum_{i=1}^{m}\left\lfloor\frac{m}{i}\right\rfloor\cdot i\right) - \sum_{i=1}^n(n \bmod i)\cdot(m\bmod j)$$

关键是后一个式子，所以拎出来单独看看

$$\sum_{i=1}^n\left(n - \left\lfloor\frac{n}{i}\right\rfloor \cdot i\right)\cdot \left(m - \left\lfloor\frac{m}{i}\right\rfloor \cdot i\right)$$ $$\sum_{i=1}^n \left(nm - \left\lfloor\frac{n}{i}\right\rfloor \cdot im - \left\lfloor\frac{m}{i}\right\rfloor \cdot in + \left\lfloor\frac{n}{i}\right\rfloor\left\lfloor\frac{m}{i}\right\rfloor \cdot i^2\right)$$ $$n^{2}m - \sum_{i=1}^{n}i\cdot \left(\left\lfloor\frac{n}{i}\right\rfloor \cdot m + \left\lfloor\frac{m}{i}\right\rfloor \cdot n\right) + \sum_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor\left\lfloor\frac{m}{i}\right\rfloor \cdot i^2$$

其中 $\sum_{i=1}^{n}i^2 = \frac{n(n+1)(2n+1)}{6}$，为什么呢？参阅：小学数学之前 n 个正整数的 a 次方之和.

注意本题的范围，上一题 RE 的情况在本题没有出现

参考文档

• 11Dimensions, 从 1 开始的数论, 洛谷 2019 年 OI 夏令营.
• OI Wiki, 莫比乌斯反演

---