数论分块

数论分块可以快速计算一些含有除法向下取整的和式（即形如 的和式）。当可以在 内计算 或已经预处理出 的前缀和时，数论分块就可以在 的时间内计算上述和式的值。

它主要利用了富比尼定理（Fubini's theorem），将 相同的数打包同时计算。

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

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

引理 1

略证：

引理 2

表示集合 的元素个数

略证：

对于 ， 有 种取值

对于 ，有 ，也只有 种取值

综上，得证

数论分块结论

对于常数 ，使得式子

成立的最大的满足 的 的值为 。即值 所在的块的右端点为 。

过程

数论分块的过程大概如下：考虑和式

那么由于我们可以知道 的值成一个块状分布（就是同样的值都聚集在连续的块中），那么就可以用数论分块加速计算，降低时间复杂度。

利用上述结论，我们先求出 的 前缀和（记作 f(j)），然后每次以 为一块，分块求出贡献累加到结果中即可。

伪代码如下：

最终得到的 即为所求的和式。

习题

1. CQOI2007 余数求和（需要一点转化和特判）

2. UVa11526 H(n)（几乎可以当做模板题）

3. POI2007 ZAP-Queries（数论分块一般配合

   莫比乌斯反演 用以进一步降低复杂度；本题需要用到 这一条莫反结论）