整除分块

整除分块
在数论中经常会出现如下表达式:
$$\sum^{N}_{i=1}\lfloor \frac{N}{i} \rfloor,N\leq10^{12}$$
显然我们直接计算的时间复杂度为$O(N)$,于是我们需要一种拥有更优时间复杂度的算法。
通过打表我们可以发现。改表达式具有一些特殊的性质。
1.$\lfloor \frac{N}{i} \rfloor$最多只有$2\sqrt{N}$种取值
证明:对于$i\leq\sqrt{N}$,只有$\sqrt{N}$种取值,对于$i>\sqrt{N}$,同样也只有$\sqrt{N}$种取值,一共$2\sqrt{N}$种取值
2.若$\lfloor \frac{N}{i} \rfloor与\lfloor \frac{N}{R} \rfloor$相等,那么这个R最大为$\lfloor\frac{N}{\lfloor \frac{N}{i} \rfloor}\rfloor$
证明链接
然后我们就可以设两个指针L和R,每次令$R = \lfloor\frac{N}{\lfloor \frac{N}{i} \rfloor}\rfloor$。然后这一段相同答案的和就是$(R-L+1)* \lfloor \frac{N}{i} \rfloor$。再令L = R + 1。因为只有$2\sqrt{N}$种不同的取值,显然整数也就被分为$2\sqrt{N}$段,所以时间复杂度为$O(\sqrt{N})$

Last modification:April 2nd, 2019 at 08:04 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment