数论分块

用处

数论分块可以快速计算一些含有除法向下取整的和式（即形如 $\sum_{i = 1}^n f(i)g(\left\lfloor\dfrac ni \right\rfloor)$ 的和式）。当可以在 $O(1)$ 内计算 $f(r) - f(l)$ 或已经预处理出 $f$ 的前缀和时，数论分块就可以在 $O(\sqrt n)$ 的时间内计算上述和式的值。它主要利用了富比尼定理$(Fubini's theorem)$ ，将 $\left\lfloor\dfrac ni\right\rfloor$ 相同的数打包同时计算。

富比尼定理

又称“算两次”，以意大利数学家圭多·富比尼（Guido Fubini）命名。 富比尼定理的积分形式：只要二重积分 $\int\int|f(x, y)|dxdy$ 有界，则可以逐次计算二重积分，并且可以交换逐次积分的顺序。 积分号也是特殊的求和号，因此在一般求和中，富比尼定理往往呈现为更换计数顺序，即交换两个求和号。 组合数学中的富比尼定理表现为，用两种不同的方法计算同一个量，从而建立相等关系。

例如这里的双曲线下整点的图片：

图中共分为了 $5$ 块，这 $5$ 块整点的最大纵坐标都相同。如果统计整点的个数，可以从纵向计数改为横向计数，直接计算$5$ 个矩形即可。

引理1

$\forall a, b, c\in\mathbb{Z}, \left\lfloor\frac{a}{bc}\right\rfloor = \left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor$

证明略(我也不会)qwq

引理2

$\forall n\in\mathbb{N}_{+}, \left|\left\{\lfloor\frac{n}{d}\rfloor\mid d\in\mathbb{N}_{+}, d\leq n \right\}\right|\leq\lfloor 2\sqrt{n}\rfloor$

$\left|V\right|$ 表示集合 $V$ 的元素个数

证明略

数论分块结论

对于常数 $n$ ， 是的式子 $\lfloor \frac ni\rfloor = \lfloor \frac nj\rfloor$ 成立的最大的满足 $i \le j\le n$ 的 $j$ 的值为 $\left\lfloor \frac{n}{\lfloor \frac ni\rfloor}\right\rfloor$ 。即值 $\lfloor \frac ni \rfloor$ 所在的块的左端点为 $\left\lfloor \frac{n}{\lfloor \frac ni\rfloor}\right\rfloor$ 。

数论分块的过程大概如下：考虑和式 $\sum_{i = 1}^{n} f(i) \lfloor \frac ni\rfloor$ 那么由于我们可以知道 $\lfloor \frac ni \rfloor$ 的值成一个块状（就是同样的值都聚集在连续的块中），那么就可以用数论分块加速计算，降低时间复杂度。

利用上述结论，我们先求出 $f(i)$ 的 前缀和（记作 $s(i) = \sum_{j = 1}^{i}f(i)$ ），然后每次以 $\left[l, r \right] = \left[ l, \left\lfloor \frac{n}{\lfloor \frac ni\rfloor}\right\rfloor\right]$ 为一块，分块求出贡献累加到结果中即可。