学习笔记——整除分块

Neck Deep / 2023-08-11 / 原文

整除分块

求$\sum_{i=1}^N \lfloor \frac Ni \rfloor,N \leq 10^{12}$

N很大，显然不能直接求。
我们需要把$\Theta (N)$转换成$\Theta(\sqrt{N})$
于是就聊到了今天的正题。

我们可以发现一个性质：对于$\lfloor \frac Ni \rfloor$,显然只有
$2\sqrt{N}$种结果。

证明很简单：

当i $\leq \sqrt{N}$时，最多有$ \sqrt{N}$种结果；

当i > $\sqrt{N}$时，$\frac Ni \leq \sqrt{N}$,最多也只有$\sqrt{N}$种结果

还有另外一个性质：当$\lfloor\frac Ni\rfloor=\lfloor\frac {N}{i'}\rfloor$时，
$max(i')$=$\lfloor\frac {N}{\lfloor\frac {N}{i}\rfloor}\rfloor$。

证明不简单：

设$\lfloor \frac Ni \rfloor=k$,则$N=ki+p(1\leq p < i)$.

设$\lfloor \frac{N}{i+d} \rfloor =k$,则$ k*(i+d)+p'=N $.

所以$p'=p-kd$.则d最大值为$\lfloor \frac pk \rfloor$.

所以

$\begin{aligned} i'&=i+d_{max} \\ &=i+\lfloor \frac pk \rfloor \\&=i+\left \lfloor \frac {N \;mod\; i}{\lfloor \frac Ni \rfloor} \right \rfloor \\ &=i+\left \lfloor \frac {N-\lfloor \frac Ni\rfloor i}{\lfloor \frac Ni \rfloor} \right \rfloor \\ &=\left \lfloor i + \frac {N-\lfloor \frac Ni\rfloor i}{\lfloor \frac Ni \rfloor} \right \rfloor \\ &=\left \lfloor \frac{\lfloor \frac Ni \rfloor i}{\lfloor \frac Ni \rfloor} + \frac {N-\lfloor \frac Ni\rfloor i}{\lfloor \frac Ni \rfloor} \right \rfloor \\ &=\left \lfloor \frac N{\lfloor \frac Ni \rfloor} \right \rfloor \quad \quad\end{aligned}$

代码实现

两个指针$L$和$R$,$L$初始为1，每次令$R=\lfloor\frac {N}{\lfloor\frac {N}{L} \rfloor}\rfloor$,将$(R-L+1)*\lfloor\frac {N}{L}\rfloor$累加到答案中，再让$L=R+1$,不断的累加.(类似于分块)

for(int l=1,r;l<=n;l=r+1)
{
    r=n/(n/l);
    ans+=(r-l+1)*(n/l);
}

复杂度

$\lfloor\frac {N}{L}\rfloor$最多只有$2\sqrt{N}$种可能，且单调递减；

则最多只有$2\sqrt{N}$个取值不同的段。故复杂度为$\Theta(\sqrt{N})$

拓展

有的时候(usually),推出来的式子远比这复杂,可能会与某些积性函数相乘。

此时,当我们每完成一个块,其积性函数的值也跳了一个区间.

此时,就需要乘上那个区间的函数值.

用前缀和维护即可

参考文献()

1 2