关于整除分块

· · 算法·理论

前言

这是一个在数论中很常用的技巧，它通常可以将 O(n) 的时间复杂度优化到大概 O(\sqrt{n}) 的复杂度。在这里重点讲述一下关于它的一些性质的证明。

引入

给定一个正数 n，求：

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

一般我们都会选择 O(n) 的暴力枚举，可如果是 n \le 10^9 的数据范围呢？这么做岂不是会超时？

整除分块就能有效地将该问题进行优化。

证明性质

首先我们可以先让 n=15，并暴力打表输出，看看是否可以从中找到一些规律（当然证明是很有必要的，要不然写来干啥呢）。

#include<iostream>
using namespace std;
int n=15;
int main(){
    for(int i=1;i<=n;i++){
        cout<<i<<' '<<n/i<<endl;
    }
}

输出：

i=1:  15
i=2:  7
i=3:  5
i=4:  3
i=5:  3
i=6:  2
i=7:  2
i=8:  1
i=9:  1
i=10: 1
i=11: 1
i=12: 1
i=13: 1
i=14: 1
i=15: 1

打完表后发现输出的值是有规律的，它满足以下性质：

简单一点的性质

  1. 单调性
    这是肯定的，随着 i 的增大，可以明显发现：对于一个 i（i>1），\lfloor \dfrac{n}{i} \rfloor 的值肯定不大于 \lfloor \dfrac{n}{i-1} \rfloor，即整个序列是非严格单调递减的（这应该都知道吧）。

  2. 分段性
    这也是显然的，随着 i 的增大且序列单调不上升，输出的值肯定会变得越来越稠密，自然会形成数值按段分布（显然只有一段）的情况。

较难证明的性质

为方便描述先申明一句，以下的 \sqrt{n} 都是向下取整后的结果。

  1. 对于任意一个 n，\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor 中不同的数值出现的个数是有限的。

    那最多出现多少个不同的数呢？这里先给出结论：最多出现 2 \sqrt{n} 个。

    我们先把 1 \dots n 分为两段来考虑，即：\sum_{i=1}^{\sqrt n} 与 \sum_{i= \sqrt{n}+1 }^n 两部分。

    先考虑第一部分：由于 1 \dots \sqrt{n} 中只有 \sqrt{n} 项，所以该部分最多只出现 \sqrt{n} 个数。

    再思考第二部分。虽然 \sqrt{n}+1 \dots n 明显超过 \sqrt{n} 项（如果 n 大点，甚至接近 n 项），但容易发现：\lfloor \frac{n}{\sqrt{n}+1} \rfloor \le \sqrt{n}，而 \lfloor \frac{n}{\sqrt{n}+1} \rfloor = 1，因此该部分中数值的范围是 1 \dots \sqrt{n}，所以该部分不同的数最多也只有 \sqrt{n} 个。

    因此整合一下两部分，总的不同的数的个数一定不大于 2\sqrt{n} 个。
    得证。（其实也不麻烦对吧）。

  2. 每一段的边界

    这个是最难证明的，也是学习整除分块时的难点。学懂了它也就基本掌握了整除分块的原理。

    还是先给出结论：
    假设当前块的左端点为 x，引入一个函数 g(x) 为当前块的右端点。则根据性质有：\lfloor \frac{n}{x} \rfloor = \lfloor \frac{n}{g(x)} \rfloor 并有 \lfloor \frac{n}{x} \rfloor > \lfloor \frac{n}{g(x)+1} \rfloor。则该块的右端点即 g(x) 等于 \lfloor \frac{n}{\lfloor \frac{n}{x} \rfloor} \rfloor。

    下面的式子有点多，可以耐心地看。

    • 证明第一个式子：\lfloor \frac{n}{x} \rfloor = \lfloor \frac{n}{g(x)} \rfloor。

      先证明 \lfloor \frac{n}{x} \rfloor \ge \lfloor \frac{n}{g(x)} \rfloor。
      假设将 g(x) 中的下面那个下取整符号删去，即变为：\lfloor \frac{n}{\frac{n}{x}} \rfloor = x。因为去掉了下取整符号，所以 \frac{n}{x} > \lfloor \frac{n}{x} \rfloor，所以又有：\lfloor \frac{n}{\lfloor \frac{n}{x} \rfloor} \rfloor > \lfloor \frac{n}{\frac{n}{x}} \rfloor，所以有： g(x) \ge x。则：\lfloor \frac{n}{x} \rfloor \ge \lfloor \frac{n}{g(x)} \rfloor。

      再证明 \lfloor \frac{n}{x} \rfloor \le \lfloor \frac{n}{g(x)} \rfloor。
      因为 \lfloor \frac{n}{g(x)} \rfloor = \lfloor \frac{n}{\lfloor \frac{n}{\lfloor \frac{n}{x} \rfloor} \rfloor} \rfloor，若将 \lfloor \frac{n}{\lfloor \frac{n}{\lfloor \frac{n}{x} \rfloor} \rfloor} \rfloor 中第二小的下取整符号去掉，即变为：\lfloor \frac{n}{\frac{n}{\lfloor \frac{n}{x} \rfloor}} \rfloor，可以发现该式因为分母的增大（或不变）而变小了（或不变），并可以化简为：\lfloor \frac{n}{x} \rfloor。所以 \lfloor \frac{n}{\lfloor \frac{n}{\lfloor \frac{n}{x} \rfloor} \rfloor} \rfloor \ge \lfloor \frac{n}{x} \rfloor，则根据等量代换，可以得到：\lfloor \frac{n}{g(x)} \rfloor \ge \lfloor \frac{n}{x} \rfloor。

      因此，因为既有 \lfloor \frac{n}{x} \rfloor \ge \lfloor \frac{n}{g(x)} \rfloor 又有 \lfloor \frac{n}{x} \rfloor \le \lfloor \frac{n}{g(x)} \rfloor，所以：\lfloor \frac{n}{x} \rfloor = \lfloor \frac{n}{g(x)} \rfloor。
      得证。

    • 再证明第二个式子：\lfloor \frac{n}{x} \rfloor > \lfloor \frac{n}{g(x)+1} \rfloor。
      这里我们用带余除法来证明（这是在数论中非常常用的证明方式）。

      设 n=kx+r，其中 k 为商，r 为余数，且有 0 \le r < x。
      所以要证明的这个式子等价于证明：k> \lfloor \frac{n}{\lfloor \frac{n}{k} \rfloor +1} \rfloor，也等价于证明：k(\lfloor \frac{n}{k} \rfloor +1) > n（令该式为一式）。

      为证明该式，我们再设 a=bk+c，其中 0 \le c < k。带回一式有：k(b+1)>(bk+c)，化为：kb+k>bk+c，则有：k>c。因为有 c<k，该式成立。因为证得该式等于证明出了 \lfloor \frac{n}{x} \rfloor > \lfloor \frac{n}{g(x)+1} \rfloor，所以这个式子也成立。
      得证。

    因此 g(x) = \lfloor \frac{n}{\lfloor \frac{n}{x} \rfloor} \rfloor 成立，该块的右端的等于该式。

    因为之前已经证明出了不同的数的个数最多为 2 \sqrt{n}，因此我们枚举的时候可以按照上面证明出的每一块的边界跳着算，时间复杂度也就降为了大约 O(\sqrt{n})。

参考代码

#include<iostream>
using namespace std;
int n;
int main(){
    long long res=0;
    for(int l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        res+=(long long)(r-l+1)*(n/l);
    }
    cout<<res;
}

总结

该问题还是比较考数学能力的，并且在莫比乌斯反演、杜教筛等算法中都有运用，需要理解透彻。