题解 | 【模板】整除分块 #

$[模板]$

$整除分块也叫数论分块$

目标是求 $\sum_{1}^{n}{ \lfloor \frac{n}{i} \rfloor}$ 的和：

做法是将相同 $\lfloor \frac{n}{i}\rfloor$ 的连续一个区间看做一个块，例如区间 $[l,r]$ 中所有的 $i\in[l,r]$ 的 $\lfloor \frac{n}{i}\rfloor$ 的值都相同，那么我直接 $ans =ans+(r-l+1)\times \lfloor \frac{n}{i}\rfloor$

所以依次枚举区间的左边界，然后找到最大的右边界 $r$ ，然后累加 $ans$ ，最后将 $i$ 设置为 $r$ ，继续找下一个块

下面是基本代码：

int ans = 0;
for(int i = 1; i <= n; i ++){
    int l = i, r = 😀
    ans = ans + (r - l + 1) * (n / i);
    i = r;
}
cout << ans << endl;

有两个问题：

$n$ 最大可以为 $10^{12}$ ，这样枚举一个个块，虽然比直接的暴力循环优化了许多，但是能保证仍然不会超时吗？
最关键的，如果求出有边界 $r$

回答问题1：

显然时间复杂度直接与枚举的块的数量直接挂钩，如果块有 $10^{9}$ ，那依旧超时。但是，块的数量不会超过 $2\sqrt{n}$ 个

证明：

将区间 $[1,n]$ 拆分为两个区间 $[1,\sqrt{n}]$ 和 $[\sqrt{n} + 1,n]$

区间 $[1,\sqrt{n}]$ 只有 $\sqrt{n}$ 个数，那么块的数量肯定就是小于等于 $\sqrt{n}$

区间 $[\sqrt{n} + 1,n]$ 的数可能很多，例如当 $n=900$ 时， $\sqrt{n}=30$ ，那么有 $970$ 个数，但是 $\frac{n}{\sqrt{n} + 1}<\sqrt{n}$ ， $\frac{n}{n}=1$ ，它的商值的个数不会超过 $\sqrt{n}$ 个，也就是说块的数量也不会超过 $\sqrt{n}$ 个个

所以区间 $[1,n]$ 的块的数量不会超过 $2\sqrt{n}$ 个

回答问题2：

如何求有边界 $r$ ？给出结论 $r=\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor$ ，那么下面需要证明两个等式：

$\lfloor \frac{n}{l} \rfloor = \lfloor \frac{n}{r} \rfloor$
$\lfloor \frac{n}{l} \rfloor > \lfloor \frac{n}{r + 1} \rfloor$

为什么要证明等式1？因为在同一个块，那么它们的商值就一定相同

证明过程：

先证明 $\lfloor \frac{n}{l} \rfloor \geq\lfloor \frac{n}{r} \rfloor$ :

$\lfloor \frac{n}{l} \rfloor \leq\frac{n}{l}$ ，那么两边取倒数得到 $\frac{1}{\lfloor \frac{n}{l} \rfloor} \geq\frac{l}{n}$ ，然后两边同时乘以 $n$ ，得到 $\frac{n}{\lfloor \frac{n}{l} \rfloor} \geq\ l$

因为 $r=\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor$ ，因为 $l$ 为整数，那么 $r=\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor$ ，所以 $r\geq l$

得到 $\frac{n}{l} \geq \frac{n}{r}$ ，即 $\lfloor \frac{n}{l} \rfloor \geq \lfloor \frac{n}{r} \rfloor$

在证明 $\lfloor \frac{n}{l} \rfloor \leq\lfloor \frac{n}{r} \rfloor$ ：

因为 $r=\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor$ ，两边同时取倒数，得到 $\frac{1}{r} \geq \frac{\lfloor \frac{n}{l} \rfloor}{n}$ ，两边同时乘以 $n$ ，得到 $\frac{n}{r} \geq \lfloor \frac{n}{l} \rfloor$

然后 $\frac{n}{r} \geq \lfloor \frac{n}{l} \rfloor$ 两边在同时取整数，得到 $\lfloor \frac{n}{r} \rfloor \geq \lfloor \lfloor \frac{n}{l} \rfloor \rfloor$ ，因为 $\ \lfloor \frac{n}{l} \rfloor$ 已经时整数了，所以直接是 $\lfloor \frac{n}{r} \rfloor \geq \lfloor \frac{n}{l} \rfloor$ ，即 $\lfloor \frac{n}{l} \rfloor \geq \lfloor \frac{n}{r} \rfloor$

那么 $\lfloor \frac{n}{l} \rfloor = \lfloor \frac{n}{r} \rfloor$ 得到证明

那为什么要证明等式2？因为这个有区间边界 $r$ 肯定要最大，要不然这个块就没有取完整，例如 $[5, 10]$ 是一个块，但是取的 $r$ 为 $7$ ，那肯定就不对

首先令 $k= \lfloor \frac{n}{l} \rfloor$ ，即证明 $\lfloor \frac{n}{l} \rfloor > \lfloor \frac{n}{r + 1} \rfloor$ ，其中 $r = \lfloor \frac{n}{k} \rfloor$

$r = \lfloor \frac{n}{k} \rfloor \leq \frac{n}{k} <\lfloor \frac{n}{k} \rfloor + 1 = r + 1$ ，即 $\frac{n}{k} < r + 1$ ，那么 $\frac{n}{r + 1} < k$

所以 $\lfloor \frac{n}{l} \rfloor > \lfloor \frac{n}{r + 1} \rfloor$ ，因为 $k= \lfloor \frac{n}{l} \rfloor$ 是一个整数，那么 $\lfloor \frac{n}{l} \rfloor > \lfloor \frac{n}{r + 1} \rfloor$

所以 $\lfloor \frac{n}{l} \rfloor > \lfloor \frac{n}{r + 1} \rfloor$ 得到证明

总代码：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


signed main(){
    HelloWorld;
    
    int n; cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; i ++){
        int l = i, r = (n / (n / i));
        ans = ans + (r - l + 1) * (n / i);
        i = r;
    }
    cout << ans << endl;
    return 0;
}