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

unityloverz · 发表于 2022-1-29 11:14

前言

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

一、整数分块

1、引例

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

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

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

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

证明

可以将  的值分成小于  和大于等于  的两部分，如下：
（1）当  时，最多 $\sqrt n-1$ 个值。
（2）当 $g(x) \ge \sqrt n$ 时，则 $\sqrt n \le \lfloor \frac n x \rfloor \le \frac n x$ ，从而推导得出，所以这种情况下  范围为 $[1, \sqrt n]$ ，即最多  个值，自然  也就最多  个值。

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

1、单调性

如图所示，代表的是函数 $g'(x) = \frac {25} x$ 的图像。这是一个单调不增的函数，即随着  的增大， $g'(x)$ 越来越小。

  的单调性和 $g'(x) = \frac n x$ 是一致的，所以  也是单调不增的。
2、连续性

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

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

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

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

1）当时，直接枚举个数，区间长度为1，即： $[x,x]$ ；
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"/>
可以逆序枚举，得到 $x = \lfloor \frac n {g(x)} \rfloor$ 代表所在区间的右端点，由于所有的区间连续，左端点可以由上一个区间的右端点加一得出。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;
}
}

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

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

1、原始分块

【例题1】给定，求

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

【例题2】给定，求 $\sum_{i=1}^ni\lfloor \frac k i \rfloor\\$

我们令 $f(x) = x$ , $g(x) = \lfloor \frac k x \rfloor$ ，则有：

$\sum_{i=1}^nf(i)g(i) \\$
对于这个函数，划分出 $f(x)$ 的区间，如下：

我们发现对于一段连续的 $\lfloor \frac k x \rfloor$ 值相同的区间，我们要求的是：

$\sum_{i=l}^r i \\$
利用差分法 + 前缀和就可以在 $O(1)$ 的时间内求出来了。
然后就是和【例题1】一样的相乘累加和问题了。
3、模和分块

【例题3】给定，求 $\sum_{i=1}^n (k \ mod \ i)$ 。

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

$\begin{aligned}\sum_{i=1}^n (k \ mod \ i) &= \sum_{i=1}^n (k - i\lfloor \frac k i \rfloor) \\ &= \sum_{i=1}^nk - \sum_{i=1}^ni\lfloor \frac k i \rfloor \\ &= nk - \sum_{i=1}^ni\lfloor \frac k i \rfloor \end{aligned} \\$
这样就转换成了前缀和分块问题了。

		自动登录	找回密码
密码			立即注册

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

本帖子中包含更多资源