整除分块,是指对ni\left\lfloor \frac{n}{i}\right\rfloor的相同的数之间进行分类的方法。其实分块是指连续形式的分类方法,换句话说是给定区间的分类,其对应的另一个技术叫筛法,筛法是不限于连续形式,而是在一个范围内进行分类的方法。这是两种在数学上分类方法的区别。而整除分块又是特指对ni\left\lfloor \frac{n}{i}\right\rfloor形式的分块。因此,这是一个目的十分明确的技术。

首先以n=20n=20为例,举例不同ii下,ni\left\lfloor \frac{n}{i}\right\rfloor的结果:

ii ni\left\lfloor \frac{n}{i}\right\rfloor
1 20
2 10
3 6
4 5
5 4
6 3
7 2
8
9
10
11 1
12
13
14
15
16
17
18
19
20

可以看见,不变的一块的长度越来越大。这只是一个例子,直观了解什么是整除分块,以及其必要性。下面来正式说明整除分块:

定理:给定nn,对于不同ii而言,令iki_k为恰为ni\left\lfloor \frac{n}{i}\right\rfloor发生变化的位置。那么有:

$$i_{k+1}=\left\lfloor n/{\left\lfloor n/i_k \right\rfloor }\right\rfloor+1 $$

证明:

对于给定的ni+di=k\left\lfloor\frac{n}{i+di}\right\rfloor=k,则ki+r=n=k(i+di)+rki+r=n=k(i+di)+r^\prime

n=ki+kdi+rn=ki+kdi+r^\prime,即r=kdi+rr=kdi+r^\prime,由r0rkdi=r0r^\prime\geq0\Rightarrow r-kdi=r^\prime\geq0,得到dirkdi\le\frac{r}{k}

注意整数关系,必有dirkdi\le\lfloor\frac{r}{k}\rfloor,也即didi的最大值为rk\lfloor\frac{r}{k}\rfloor

那么保持kk不变的上限为$i+{\rm di}_{max}=i+\left\lfloor\frac{r}{k}\right\rfloor=\left\lfloor i+\frac{n-ki}{k}\right\rfloor=\left\lfloor\frac{n-ki+ki}{k}\right\rfloor=\left\lfloor\frac{n}{k}\right\rfloor=\lfloor n/{\lfloor n/i \rfloor}\rfloor$。

故$i_{k+1}=\left\lfloor n/{\left\lfloor n/i_k \right\rfloor }\right\rfloor+1$恰好为下一个变化的位置。

证明可以不看,主要的思想是源于除法结构的最值讨论。可以说,根本的原因是余数的最值规律。因此,光观察而尝试得出结论是十分困难的,这个只能是记忆,或者尝试理解证明过程。在此就并不推荐纯计算机方向的acmer参与,而acm-mather则应该了解证明。

因此使用R = n/(n/L) + 1来表示下一头端点就是整除分块的根本目的。有且只需记住这样操作即可。

实际上的整除分块的复杂度是O(N)O\left(\sqrt{N}\right)因此一般数据范围是10910^9以内。

0 comments

No comments so far...