引入

在数论问题中，我们经常需要计算如下形式的和： 如果暴力枚举每一个 i，时间复杂度为 O(n)，当 n 较大时无法接受。

观察 的值，可以发现其取值种类数远小于 n，并且相同的取值是连续的一段。

i 1 2 3 4 5 6 7 8 9 10 11 12
12 6 4 3 2 2 1 1 1 1 1 1

以 n = 12 为例， 只有 6 种不同的取值。

数论分块（又称整除分块）就是利用这个性质，将连续的、 相同的一段 i 一起计算，从而大幅降低时间复杂度。

核心结论

取值种类数

（1 ≤ i ≤ n）的取值种类数为 。

证明

分两种情况讨论：

  • 当 时，i 最多有 种取值，故 最多有 种取值。
  • 当 时，，故 最多有 种取值。

综合两种情况，取值种类数为 。

块的右端点

对于给定的 i，所有满足 的最大的 j 为

证明

设 ，则 。

那么满足 的最大的 j 就是满足 的最大的 j，即 。

由于 j 取整数，故 。

证毕。

算法实现

有了上述结论，我们就可以从 l = 1 开始，每次计算出当前块的右端点 ，然后将 [l, r] 这一段一起计算，下一轮令 l = r + 1 继续。

基本形式

计算 ：

1
2
3
4
5
6
7
8
long long solve(long long n) {
  long long ans = 0;
  for (long long l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);
    ans += (r - l + 1) * (n / l);
  }
  return ans;
}

时间复杂度 。

带系数的形式

若要计算 ，其中 f(i) 的前缀和 可以快速求出，则：

1
2
3
4
5
6
7
8
long long solve(long long n) {
  long long ans = 0;
  for (long long l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);
    ans += (S(r) - S(l - 1)) * (n / l);
  }
  return ans;
}

时间复杂度同样为 （不考虑预处理前缀和的时间）。

二维形式

计算 时，需要对 和 同时分块。

每一块的右端点取两者的较小值：

1
2
3
4
5
6
7
8
long long solve(long long n, long long m) {
  long long ans = 0, lim = std::min(n, m);
  for (long long l = 1, r; l <= lim; l = r + 1) {
    r = std::min(n / (n / l), m / (m / l));
    ans += (r - l + 1) * (n / l) * (m / l);
  }
  return ans;
}

时间复杂度 。

例题

余数之和

例题：洛谷 P2261 [CQOI2007] 余数之和。

题意简述

给定 n, k，求 。

算法分析

由取模的定义可得 代入原式 后面的部分就是 f(i) = i 时的带系数形式，，数论分块即可。

注意枚举上界应为 min (n, k)，因为当 i > k 时 ，不产生贡献。

时间复杂度 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using lint = long long;

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  lint n, k;
  std::cin >> n >> k;
  lint ans = n * k, lim = std::min(n, k);
  for (lint l = 1, r; l <= lim; l = r + 1) {
    r = std::min(lim, k / (k / l));
    ans -= (k / l) * (r - l + 1) * (l + r) / 2;
  }
  std::cout << ans << '\n';
  return 0;
}

约数个数和

例题：洛谷 P3327 [SDOI2015] 约数个数和。

题意简述

设 d(n) 表示 n 的约数个数，给定 n, m，求

算法分析

有一个经典结论： d(ij) = ∑x ∣ i∑y ∣ j[gcd (x, y) = 1]

证明

晚点写。

代入可得 交换求和顺序 将 [gcd (x, y) = 1] 替换为 ∑d ∣ gcd (x, y)μ(d)，展开后交换求和顺序 令 ，则 预处理 μ 前缀和后，外层对 d 数论分块，内层 g 也用数论分块预处理即可。

时间复杂度 （T 为询问次数）。