整除分块学习笔记

整除分块,又称数论分块,常被用于数论函数求和以及莫比乌斯反演中。

经典问题

计算$\sum_{i = 1}^{n} \lfloor \frac{n}{i} \rfloor$。这个问题显然有一种$O(n)$的求法,但是当$n > 10^8$的时候效率会变得十分低。所以我们考虑下取整函数的性质。

求解方法

首先我们可以来观察一下$\{ \lfloor \frac{n}{i} \rfloor \} $这个序列。

假设$n = 10$,这个序列就变成了$\{ 10, 5, 3, 2, 2, 1, 1, 1, 1, 1 \}$。

假设$n = 15$,这个序列就是$\{  15, 7, 5, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1 \}$。

依次类推,我们可以写出很多这样的序列。观察这个序列,我们发现这个序列是非严格递减的,也就是满足$a_{i+1} \leq a_i$,并且可以作一个划分,使得每一个划分区间内的值相等,比如$n = 15$的时候,可以这样划分:

$$ \{  (15), (7), (5), (3, 3), (2, 2), (1, 1, 1, 1, 1, 1, 1, 1) \}  $$

其实对于任意一个$i$,我们可以算出$\lfloor \frac{n}{i} \rfloor$在这个序列中出现了几次——我们可以用$\lfloor \frac{n}{ \lfloor \frac{n}{i}  \rfloor } \rfloor$ 得到取值为$\lfloor \frac{n}{i} \rfloor$的最大的那个$i$(目前还不能给出详细的证明,读者可以多写几个序列验证这个结果,这个结论会在很多地方用到)。所以,这种题目可以这样求解:对于$\lfloor \frac{n}{i} \rfloor$的每个取值,对应的$i$是一个区间,枚举$\lfloor \frac{n}{i} \rfloor$的取值,每个取值对答案的贡献为区间长度和$\lfloor \frac{n}{i} \rfloor$的乘积。

显然这样时间效率是比$O(n)$更优的,因为$O(n)$的算法中同一个取值可能被枚举多次,但是到底优多少,需要分析一下对于$1 \leq i \leq n$,存在多少种$\lfloor \frac{n}{i} \rfloor$的取值,因为时间复杂度就是这个取值的个数。

时间复杂度分析

对于正整数$n$:

对于所有满足$1 \leq i \leq \sqrt{n}$的$i$,能得到的$\lfloor \frac{n}{i} \rfloor$的取值最多$\sqrt{n}$种;对于$i >\sqrt{n} $,可以得到$\lfloor \frac{n}{i} \rfloor \leq \frac{n}{i} < \sqrt{n}$,又因为$\lfloor \frac{n}{i} \rfloor$是正整数,只能在$1, 2, \cdots, \lfloor \sqrt{n} \rfloor$中取值,所以最多有$\sqrt{n}$个。综上所述,对于$1 \leq i \leq n$,最多存在$2 \times \sqrt{n}$种$\lfloor \frac{n}{i} \rfloor$的取值。

所以时间复杂度为$O(\sqrt{n})$。

例题

题目链接:Luogu 2261 – 「CQOI 2007」余数求和

这一题输入$n$和$k$,要求$\sum_{i = 1}^{n}  (k \bmod i) $。因为$k \bmod i = k – i \times \lfloor \frac{k}{i} \rfloor$,所以原式可以化简为:

$$ \sum_{i=1}^{n} = \sum_{i=1}^{n} k – i \times \lfloor \frac{k}{i} \rfloor $$

我们可以枚举$\lfloor \frac{k}{i}  \rfloor$的取值,然后计算每个取值区间对答案的贡献。这里要注意$\lfloor \frac{k}{i}  \rfloor = 0$的时候要特判。

我们观察到其实整除分块实质相当于右指针在$[1,n]$上跳动,每次跳动之后的位置和上一个位置中间是一个取值相同的区间,需要注意右指针不能跳出$n$,也就是说最后一个取值区间可能是不能完整取到的。

参考资料以及拓展阅读

说点什么

avatar
50
  Subscribe  
提醒