整除分块

引子

整除分块比较经典的一个例题

求$\sum _{i=1}^n\lfloor \frac{n}{i}\rfloor$,$n<={10}^{12}$

上取整也是一样的

如果我们直接暴力求的话， 时间复杂度是$O(n)$， 肯定过不了， 于是就引出了整除分块的方法

整除分块

我们知道， 在整除意义下$n/i$可能等于$n/j$，而且i, j之间的数必然和i,j的结果相同， 也就是说， $\lfloor \frac{n}{i}\rfloor$相同的i必然分布在连续的一段区间内， 那么我们统计答案时只需要统计每个连续区间的长度和端点就可以了， 可以证明这样的区间一共有$O(\sqrt{n})$个

时间复杂度的证明

分两种情况

1. $i<=\sqrt{n}$

   对于 $i<=\sqrt{n}$ , 假设每个i的结果都不一样， 最多也只有 $\sqrt{n}$ 种不同的结果

2. $i>\sqrt{n}$

   对于 $i>\sqrt{n}$, $\lfloor \frac{n}{i}\rfloor$分布在 $[0,\sqrt{n}-1]$，也就是最多只有 $\sqrt{n}$ 种

证毕， 整除分块的时间复杂度为$O(\sqrt{n})$

实现

既然我们已经证明了时间复杂度， 那接下来我们就想办法实现它

既然结果相同的i分布在连续的区间内， 那我们就通过两个端点l， r确定区间， 然后不断移动l， r就可以了

初始时， 设l = 1

1. 计算出$res=\lfloor \frac{n}{l}\rfloor$
2. 确定r， $r=\lfloor \frac{n}{res}\rfloor$
3. 统计答案, $l=r+1$
4. 重复上述过程， 直到$l>n$

关于第2步的证明

假设当前答案为$res$， 那么所有满足条件的$i$满足

$i\times res+d=n,0\le d=n\mathrm{\%}i<i$

那么$i$最大时， $d=0$， 此时$i=\frac{n}{res}$， 如果不能整除， 显然应该下取整

所以$r=\lfloor \frac{n}{res}\rfloor$， 得证

代码就不上了

Update

更新一下向上取整的情况， 感觉较向下取整还是复杂了些。

初始时， 设l = 1

1. 计算出$res=\lceil \frac{n}{l}\rceil$
2. 确定r, 如果$res=1$，$r=n$, 否则$r=\lceil \frac{n}{res-1}\rceil$
3. 统计答案， $l=r+1$
4. 重复上述过程， 直到$l>n$

关于第二步的证明

假设当前答案为$res$，那么所有满足条件的$i$满足

$res-1<\frac{n}{i}\le res$

转换成i的范围

$\frac{n}{res}\le i<\frac{n}{res-1}$

把i转换成范围内的整数

$\lceil \frac{n}{res}\rceil \le i<\lceil \frac{n}{res-1}\rceil$

即

$\lceil \frac{n}{res}\rceil \le i\le \lceil \frac{n}{res-1}\rceil -1$

所以i最大为$\lceil \frac{n}{res-1}\rceil -1$， 得证