数论分块可以解决一些带有 除法向下取整 的和式。例如经典的整除求和问题：

$$\sum_{i = 1}^n \lfloor \frac{n}{i} \rfloor$$

其中，$\lfloor \dfrac{n}{i} \rfloor$ 表示 $n$ 除以 $i$ 并向下取整，$n$ 是给定的一个整数。

直接暴力计算的时间复杂度为 $O(n)$。如果使用整除分块，时间复杂度降为 $O(\sqrt{n})$。

分析过程

以 $n = 8$ 为例：

对第二行求和，有 $\sum_{i = 1}^8 \lfloor \frac{8}{i} \rfloor = 20$。

观察表格，我们发现 8/i 的值是逐步变小的，并且存在一些相同的值，如果我们能很快地知道下一次 8/i 在哪变化，就可以跳过中间的重复枚举过程，能大大减小计算量。

这里运用到分块的思想，将 8/i 相同的部分分到一块。显然，每一块的求和就是块的大小和内部值的乘积。

实际上，数论分块的本质是利用了富比尼定理（Fubini’s theorem）。

富比尼定理：其积分形式是，如果二重积分 $\iint|f(x,y)|\,dx,\, dy$ 有界，就可以逐次计算二重积分，并且可以交换逐次积分的顺序，即 $\iint|f(x,y)|\,dx \, dy= \iint|f(x,y)|\,dy,\,dx$。由于积分号是特殊的求和符号，因此在一般求和中，富比尼定理也表现为更换计数顺序，即交换两个求和号。在组合数学中，富比尼定理表现为用不同的方法计算同一个量，从而建立相等关系。

整除分块结论

给定每个块的左端点 $L$，其右端点 $R = \lfloor{\dfrac{n}{\lfloor \frac{n}{L} \rfloor} \rfloor}$。

证明: 这个分块的内部值为 $k = \lfloor \dfrac{n}{i} \rfloor$，可知 $k \leq \dfrac{n}{i}$。
$\therefore \lfloor \dfrac{n}{k} \rfloor \geq \lfloor \dfrac{n}{\frac{n}{i}} \rfloor = \lfloor i \rfloor = i$
$\therefore$ 这个块的右端点，即使得 $\lfloor \dfrac{n}{L} \rfloor = \lfloor \dfrac{n}{R} \rfloor$ 的 $R$ 的最大值为 $i = i_{max} = \lfloor \dfrac{n}{k} \rfloor = \lfloor{\dfrac{n}{\lfloor \frac{n}{L} \rfloor} \rfloor}$
$Q.E.D.$

在程序设计中，就可以写为 R = n / (n / l)

参考代码

以下面问题为例：

$$\sum_{i = 1}^n \lfloor \frac{n}{i} \rfloor$$

#include <iostream>
#define ll long long

using namespace std;

ll n,L,R,ans;

int main()
{
    cin >> n;
    for (L = 1; L <= n; L = R+1)
    {
        R = n / (n / L);
        ans += (R - L + 1) * (n / L);
    }
    cout << ans;
}

例题

Luogu P9611 【CERC2019】Zeldain Garden

题目描述：给定 $l,r$，求 $[l,r]$ 中所有数的因数个数之和。其中 $1 \leq l,r \leq 10^{12}.$

考虑 前缀和 思想，计算出 solve(x) 表示从 $1$ 到 $x$ 的所有数字的因数个数之和。那么答案就是 solve(r) - solve(l-1)。

从 $1$ 到 $x$，考虑其中每一个数字对答案的 贡献，它代表每一个数字是范围内多少个数字的因数，即它给答案增加了多少。例如，$1$ 是中间每一个数的因数，那么它就为答案做出了 $x$ 的贡献；$2$ 是中间所有偶数的因数，那么它就为答案做出了 $\lfloor \dfrac{x}{2} \rfloor$ 的贡献……以此类推。可以得到，数字 $p$ 的贡献就是 $\lfloor \dfrac{p}{2} \rfloor$，那么答案就是 $$\sum_{i = 1}^n \lfloor \frac{n}{i} \rfloor$$

这和我们开头提到的问题一致。

#include <iostream>
#include <cctype>
#include <vector>

#define ll long long

ll read()
{
    ll x = 0, f = 1;
    char ch = 0;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

ll n, m;

ll solve(ll n)
{
    ll L, R, ans = 0;
    for (L = 1; L <= n; L = R + 1)
    {
        R = n / (n / L);
        ans += (R - L + 1) * (n / L);
    }
    return ans;
}

int main()
{
    n = read();
    m = read();
    printf("%lld\n", solve(m) - solve(n - 1));
    return 0;
}

Luogu P2261 【CQOI2007】余数求和

题目描述：给出正整数 $n$ 和 $k$，请计算
$$G(n, k) = \sum_{i = 1}^n k \bmod i$$
其中 $k\bmod i$ 表示 $k$ 除以 $i$ 的余数。

这道题是简单数论分块的变式，我们变形原式：
$$
\sum_{i = 1}^n k \bmod i = \sum_{i = 1}^n k – i \times \lfloor \frac{k}{i} \rfloor = n \times k – \sum_{i = 1}^n i \times \lfloor \frac{k}{i} \rfloor
$$

注意到右半部分的求和即数论分块的变形，只需重新计算每一块的值，是

(k / L) * (R - L + 1) * (R + L) / 2

这道题还有两个坑点：

• 题目中没有提到 $n,k$ 的大小关系。分析得知，如果 $n > k$，那么 $i$ 枚举到 $k$ 以上时，$\lfloor \dfrac{k}{i} \rfloor = 0$ 恒成立，只需枚举到 $k$ 即可；如果 $n < k$，因为求和符号 $i$ 也只枚举到 $n$。综上所述，只需枚举到 $\min(n,k)$ 即可。
• 计算块的右端点 R 的时候，R = k / (k / L) 有可能超过 $n$ 导致边界错误，只需取 min( k / ( k / L), n)

#include <iostream>
#include <cctype>
#define ll long long

using namespace std;

ll read()
{
    ll x = 0, f = 1;
    char ch = 0;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

ll n, k;
ll L, R, ans;

int main()
{
    n = read();
    k = read();
    ans = n * k;
    n = min(n, k);
    for (L = 1; L <= n; L = R + 1)
    {
        R = min(k / (k / L), n);
        ans -= (k / L) * (R - L + 1) * (R + L) / 2;
    }
    printf("%l ld\n", ans);
    return 0;
}