整数分块 —— 完美的根号n算法

unityloverz

前言

整数分块这个算法的内容比较独立，虽然把它归到数论一栏，但是有一些简单的高中数学基础也能看懂。利用的是整数除法的性质，将一个  的算法优化成 。

一、整数分块

1、引例

【例题1】给定 ，求  
其中 是指实数  的整数部分。

我们可以直接根据题意，写出一个循环语句，代码如下：
#include <iostream>
using namespace std;
int main() {
    int n, k;
    while(scanf("%d %d", &n, &k) != EOF) {
        int ans = 0;
        for(int x = 1; x <= n; ++x) {
            ans += <span class="n">k / x;
        }
        printf("%d\n", ans);
    }
    return 0;
}
容易得知，这样做的时间复杂度是  的。而  的范围过大，所以需要对这个算法进行优化。
2、引理

为了尝试找出优化算法，我们引入如下的一个定理。

【引理1】对于  （其中  为正整数，且 ），则  不同值的个数不会超过  个。

证明

可以将  的值分成小于  和 大于等于  的两部分，如下：
（1）当  时， 最多 个值。
（2）当 时，则 ，从而推导得出 ，所以这种情况下  范围为 ，即最多  个值，自然  也就最多  个值。

综上所述， 的值不会超过  个值。
以上就是整数分块的核心。
二、整数分块的性质

1、单调性

如图所示，代表的是函数 的图像。这是一个单调不增的函数，即随着  的增大， 越来越小。



  的单调性和 是一致的，所以  也是单调不增的。
2、连续性

结合【引理1】和单调性，要把  个  映射到  个 ，必然有一部分的  值是连续相同的。 如图所示， 的情况如下：


不同颜色代表的不同整数分块，值相同的一定是连续的，所以对于每个  的值（也就是上图中的 的值）我们只需要知道一个区间即可。
3、连续区间

连续的区间表示成表格的形式，如图所示：


为了能让读者更易读懂，所以把颜色和上面的图对应上了。如何求解这些区间呢？我们可以分为两段：

• 1）当  时，直接枚举  个数，区间长度为1，即 ： ；
  
• 2）当  时，可以推导出：
  

<img sr="https://www.zhihu.com/equation?tex=g%28x%29+%3D+%5Clfloor+%5Cfrac+n+x+%5Crfloor+%5Cle+%5Cfrac+n+x+%5Clt+%5Csqrt+n+%5C%5C" alt="g(x) = \lfloor \frac n x \rfloor \le \frac n x \lt \sqrt n \\" loading="lazy" eeimg="1"/>
可以逆序枚举 ，得到 代表所在区间的右端点，由于所有的区间连续，左端点可以由上一个区间的右端点加一得出。c++ 代码实现如下：
void integerSplit(int maxx, int n, vector<Interval> &ret) {  // (1)
    ret.clear();
    double sqrtn = sqrt(n + 0.0);
    int last = 1;                                            // (2)
    for(int x = 1; x <= sqrtn; ++x) {
        if(x > maxx) {
            return;
        }
        ret.push_back( Interval(x, x) );                     // (3)
        last = x;
    }
    int intsqrtn = (int)(sqrtn + eps);                       // (4)
    int gx = intsqrtn;
    if( fabs(intsqrtn - sqrtn) < eps ) {
        --gx;
    }
   
    for(int x = gx; x >= 1; --x) {                           // (5)
        int now = n / x;                                     // (6)
        if(now > maxx) {                                     // (7)
            now = maxx;
            ret.push_back( Interval(last+1, now) );
            return ;
        }
        ret.push_back( Interval(last+1, now) );
        last = now;
    }
}

• integerSplit(int maxx, int n, vector<Interval> &ret)函数求得是 的区间，并且将每个求出来的区间存在ret数组中返回；
  
• 初始时，上一个区间的右端点为last = 1；
  
• 计算  的部分，区间长度必然为 1，即 ；
  
• 计算  的部分，这时候 ，由于是正好小于，所以要对  为完全平方数的情况减一，即代码的--gx部分；
  
• 逆序枚举 。
  
• 这里的now = n / x中的now是定义域的区间的右端点，而端点则是 last+1，这样就有了一个满足  相同的区间[last+1, now]；
  
• 如果超过定义域  的最大值，则截断后直接返回；
  

迭代完毕以后，得到的ret数组里存的，就是不超过   个的区间范围，对应的  的值是不用存的，因为无论是区间左端点，或是右端点，亦或是中间的某个值，都可以通过  求得相同的值。
三、整数分块的应用

1、原始分块

【例题1】给定 ，求

首先，利用上文给出的integerSplit函数，将所有的定义域的区间求出来存到ret数组；
然后，遍历ret数组，对于数组中每个区间，累加和到 上，核心代码如下：
ans += (r - l + 1) * (k / n);
2、前缀和分块

【例题2】给定 ，求

我们令 , ，则有：


对于  这个函数，划分出 的区间，如下：


我们发现对于一段连续的 值相同的区间 ，我们要求的是：


利用差分法 + 前缀和 就可以在 的时间内求出来了。
然后就是和【例题1】一样的相乘累加和问题了。
3、模和分块

【例题3】给定 ，求 。

对原式进行一个变换，得到：


这样就转换成了前缀和分块问题了。