整除分块

求$\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=pi+k(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}$,将$(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))$

JZTXT

学习笔记——整除分块

整除分块

代码实现

复杂度