介绍

数论分块一般用于解决 含有 $\lfloor \frac{N}{i} \rfloor$ 的求和问题。

数论分块主要利用了 $\lfloor \frac{N}{i} \rfloor$ 的取值范围相当有限的特点，所以有

$$i \leq j, ~\lfloor \frac{N}{i} \rfloor = \lfloor \frac{N}{j} \rfloor$$

这样一些求和问题就可以转化为 $(j-i+1) \times \lfloor \frac{N}{j} \rfloor$ （或者类似的形式）

时间复杂度：$O(\sqrt n)$

证明

$\forall i \leq n,$ $\exists$ 最大的 $j$ 使得 $~i \leq j \leq n$，且 $\lfloor \frac{n}{i} \rfloor = \lfloor \frac{n}{j} \rfloor$

则 $$j = \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor$$

证明：

显然 $j \leq n$，只要证 $j \geq i$：

因为 $j = \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor$，又因为 $i = \lfloor \frac{n}{\frac{n}{i}} \rfloor$ （分母没有下取整）

因为 $\lfloor \frac{n}{i} \rfloor \leq \frac{n}{i}$，所以有 $j \geq i$

例题

例1 求 $\sum\limits_{i=1}^N \lfloor \frac{N}{i} \rfloor$

以下的代码中，我们令 l,r 代表上文的 i,j

int r;
for (int l = 1; l <= n; l = r + 1) {  // 注意这里是 l = r+1
    r = n / (n / i);
    ans += (n / l) * (r - l + 1);
}

• 可以发现，数论分块的本质思想是 枚举 $\lfloor \frac{N}{i} \rfloor$ 的值。

例2 洛谷P2261 余数求和

题意

给定正整数 $n,k \leq 10^9$，求 $\sum\limits_{i=1}^n k \text{ mod } i$

题解

因为 （以下略去 下取整符号） $$k \text{ mod } i = k - \frac{k}{i} \times i$$

对于 $n > k$ 的部分，就加上 $(n-k) \times k$。

对于 $n \leq k$ 的部分，有 $$\sum\limits_{i=1}^n k \text{ mod } i = n\times k - \sum\limits_{i=1}^n \frac{k}{i} \times i$$

然后数论分块枚举 $\lfloor \frac{k}{i} \rfloor$ 的值，每个块分别用等差数列求和即可。

代码 
#include <bits/stdc++.h>
using namespace std;

ll n,k;
int main() {
    cin >> n >> k;
    ll ans = 0;
    if (n > k) {
        ans += (n-k) * k;
        n = k;
    }
    ll r;
    ans += (n*k);
    for (ll l = 1; l <= n; l = r+1) {
        r = min(n, k / (k/l));   // 注意这里取 min，因为 k/(k/l) 有可能超过n
        ans -= (k/l) * ((l+r) * (r-l+1) / 2LL);
    }
    cout << ans << endl;
}

例3 Atcoder ABC132F Small Products

题意

给定正整数 $n \leq 10^9$，$2 \leq k \leq 100$，求满足以下条件的序列数量：

  1. 长度为 $k$
  2. 任意两个相邻元素的乘积 $\leq n$

答案对 $10^9+7$ 取模。

题解

很容易发现 dp 思路：

设 $dp[i][j]$ 为：当前用到第 $i$ 个元素，结尾的元素的值为 $j$ 的数量。则答案为 $\sum\limits_{j=1}^{n}dp[k][j]$

但是 $n \leq 10^9$，dp数组开不了这么大。

我们可以考虑只将 dp[][] 的第二维开到 $\sqrt n$ 的大小，对于 $j > \sqrt n$ 的部分用数论分块解决。

令 $m = \sqrt n$，且维护前缀和 $sum[i][j] = \sum\limits_{k=1}^j dp[i][j]$，转移方程有：

$$dp[i][1] = \sum\limits_{j=1}^n dp[i-1][j] = \sum\limits_{j=1}^m dp[i-1][j] + \sum\limits_{j=m+1}^n dp[i-1][j]$$

其中，

$$\forall j > m, ~dp[i-1][j] = \sum\limits_{k=1}^{\lfloor \frac{n}{j} \rfloor} dp[i-2][k]$$

会发现，对于不同的 $j$，$\lfloor \frac{n}{j} \rfloor$ 的取值相当有限，所以可以用数论分块。所以有：

$$dp[i][1] = sum[i-1][j] + \sum\limits_{j=m+1}^n \sum\limits_{k=1}^{\lfloor \frac{n}{j} \rfloor} dp[i-2][k] = sum[i-1][j] + \sum\limits_{j=m+1}^n sum[i-2][\frac{n}{j}]$$

第二项用数论分块处理即可，注意到随着 $j$ 的增大，$\frac{n}{j}$ 逐渐减小，所以可以反着枚举 $j$ （即 $j = m~…~1$）

最后，答案就是 $dp[k+1][1] = \sum\limits_{j=1}^{n}dp[k][j]$

代码 
#include <bits/stdc++.h>
using namespace std;

ll n,k,m;
ll dp[103][31642];
ll sum[103][31642];

int main() {
    fastio;
    cin >> n >> k;

    m = sqrt(n);
    for (int i = 1; i <= m; i++) dp[1][i] = 1, sum[1][i] = sum[1][i-1] + 1;
    for (int i = 1; i <= m; i++) dp[2][i] = n/i, sum[2][i] = (sum[2][i-1] + dp[2][i]) % mod;

    for (int i = 3; i <= k+1; i++) {
        ll cur = 0;
        ll l = m+1,r;
        for (int j = m; j >= 1; j--) {  //倒序枚举 j
            dp[i][j] = sum[i-1][m];
            if (n/j <= m) {  // 注意这里需要特判，否则 n/j <= m 是有可能的，导致RE
                continue;
            }
            r = min(n/j, n / (n/l));
            cur = (cur + ((r-l+1) * (sum[i-2][n/l]) % mod)) % mod;
            l = r + 1;
            dp[i][j] = (dp[i][j] + cur) % mod;
        }
        for (int j = 1; j <= m; j++) sum[i][j] = (sum[i][j-1] + dp[i][j]) % mod;
    }
    ll ans = dp[k+1][1];
    cout << ans << endl;
}