数论分块

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

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

富比尼定理

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

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

双曲线下整点

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

引理 1

略证:

关于证明最后的小方块

QED 是拉丁词组“Quod Erat Demonstrandum”(这就是所要证明的)的缩写,代表证明完毕。现在的 QED 符号通常是 或者 。(维基百科

引理 2

表示集合 的元素个数

略证:

对于 种取值

对于 ,有 ,也只有 种取值

综上,得证

数论分块结论

对于常数 ,使得式子

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

证明

,可以知道

过程

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

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

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

伪代码如下:

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

例题:UVa11526 H(n)

题意: 组数据,每组一个整数 。对于每组数据,输出

思路:如上推导,对于每一块相同的 一起计算。时间复杂度为

参考实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
long long H(int n) {
  long long res = 0;  // 储存结果
  int l = 1, r;       // 块左端点与右端点
  while (l <= n) {
    r = n / (n / l);  // 计算当前块的右端点
    res += (r - l + 1) * 1LL *
           (n / l);  // 累加这一块的贡献到结果中。乘上 1LL 防止溢出
    l = r + 1;  // 左端点移到下一块
  }
  return res;
}
N 维数论分块

求含有 的和式时,数论分块右端点的表达式从一维的 变为 ,即对于每一个块的右端点取最小(最接近左端点)的那个作为整体的右端点。可以借助下图理解:

多维数论分块图解

一般我们用的较多的是二维形式,此时可将代码中 r = n / (n / i) 替换成 r = min(n / (n / i), m / (m / i))

习题

  1. CQOI2007 余数求和(需要一点转化和特判)

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

  3. POI2007 ZAP-Queries(数论分块一般配合 莫比乌斯反演 用以进一步降低复杂度;本题需要用到 这一条莫反结论)


评论