数论分块

数论分块可以快速计算一些含有除法向下取整的和式（即形如 $\sum_{i = 1}^{n}f(i) \cdot g\left(\lfloor \dfrac{n}{i} \rfloor \right)$ 的和式）。当可以在 $O(1)$ 内计算 $f_r - f_l$ 或已经预处理出 $f$ 的前缀和时，数论分块就可以在 $O(\sqrt n)$ 的时间内计算上述和式的值。

它主要利用了富比尼定理（Fubini’s theorem），将 $\lfloor \dfrac{n}{i} \rfloor$ 相同的数打包同时计算。

数论分块结论

对于常数 $n$，使得式子：

$$\left \lfloor \dfrac{n}{l} \right \rfloor = \left \lfloor \dfrac{n}{r} \right \rfloor$$

成立的最大的满足 $l \leq r \leq n$ 的 $r$ 是 $\left \lfloor \dfrac{n}{\lfloor \frac{n}{l} \rfloor} \right \rfloor$。即值 $\left \lfloor \dfrac{n}{l} \right \rfloor$ 所在的块对应的右端点为 $r = \left \lfloor \dfrac{n}{\lfloor \frac{n}{l} \rfloor} \right \rfloor$

常用的转换

• $a \mod b \rightarrow a - \lfloor \dfrac{a}{b} \rfloor \cdot b$

过程

考虑和式 $\sum_{i = 1}^{n} f(i) \left \lfloor \dfrac{n}{i} \right \rfloor$

那么我们只需要每次计算一个相同的块中的值，此时就能快速的计算 $[1, n]$ 中相应的和式的值。

换言之对于 $[l, r]$ 中的和，我们先计算 $[l, \left \lfloor \dfrac{n}{\lfloor \frac{n}{l} \rfloor} \right \rfloor]$ 对应的和式的和，然后再将左端点移动到下一个块的起点。这样最终就能在 $O(\sqrt n)$ 的时间计算。

一个值得注意的是：必须要在较短的时间计算出某个 $\sum_{i = l}^{r} f_i$.

Code

// 计算 $\sum_{i = l}^{r} f_i$
auto calc = [&](LL l, LL r) -> LL {
    assert(l <= r);
    LL inv2 = (P + 1) / 2;
    return (l + r) % P * ((r - l + 1) % P) % P * inv2 % P;
};

// 分块计算和式
auto block = [&](LL st, LL ed, LL num) -> LL {
    ed = min(ed, num);
    LL l = st, r = 0;
    LL res = 0;

    while (l <= ed) {
        r = min(ed, num / (num / l));
        res = (res + calc(l, r) * (n / l) % P) % P;
        l = r + 1;
    }
    return res;
};

例题

Educational Codeforces Round 5 E. Sum of Remainders

题目描述

计算 $\sum_{i = 1}^{m} n \mod i$

推导 ：

$$\begin{aligned} \sum_{i = 1}^{m} (n \mod i) &= \sum_{i = 1}^{m} (n - \lfloor \frac{n}{i} \rfloor \cdot i) \\\ &= n \times m - \sum_{i = 1}^m \lfloor \frac{n}{i} \rfloor \cdot i \\\ \end{aligned}$$

因此可以考虑用数论分块。

参考资料

OI Wiki 数论分块

知乎 严格鸽 ACM竞赛中常见的整数公式与整数分块