整除分块

问题提出

最近在学习莫比乌斯反演，发现基本上所有有关莫比乌斯反演的题目，都会涉及一个小知识点整除分块

所以在学习毒瘤莫比乌斯之前学习一下整除分块是很有必要的

然后我们就先来学习这个问题

我们来讨论一个有趣的问题

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

问题解决

显然不能直接做

经过一番冷静推理暴力打表，我们发现以下性质：

·1.\[\large \lfloor \frac Ni \rfloor\]向下取整最多只有\[2\sqrt{N}\]种取值

证明：对于\[i\le \sqrt{N}\],只有\[\sqrt{N}\]种，对于\[i>\sqrt{N},\large{\frac Ni}<\sqrt{N}\],也只有\[\sqrt {N}\]种取值，共计\[2 \sqrt{N}\]种取值

·2.设\[\large \lfloor \frac N{i‘} \rfloor\]与\[\large \lfloor \frac N{i} \rfloor\]相等，则\[i‘\]的最大值\[max(i‘)= \large \left \lfloor \frac N{\left \lfloor \frac Ni \right \rfloor } \right \rfloor\]

证明：设\[\large{ \lfloor \frac Ni \rfloor}=k\]，于是可以写成\[ki+p=N,1\le p<i\]的形式，若有\[\large{\lfloor \frac N{i+d} \rfloor}=k\]，于是\[k(i+d)+p‘=N\] ，即有\[p‘=p-kd\]，则\[能得到的最大值为d能得到的最大值为 \large \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\Box\end{aligned}\]

然后，设两个指针L,R，L的初始值为1，每次令\[\large R=\left \lfloor \frac N{\lfloor \frac NL \rfloor} \right \rfloor\]将\[\large (R-L+1)\cdot \lfloor \frac NL \rfloor\]由于\[\large \lfloor \frac NL \rfloor\]只有\[2 \sqrt{N}\]种取值，且单调递减，这最多只有\[2 \sqrt{N}\]个取值不同的，时间复杂度\[（）O（\sqrt{N}）\].

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

与其他函数的联系

• 有时候，可能推出来的式子不一定就是一个很裸的整除分块，可能会与某些积性函数相乘，如：μ,φμ,φ...... 这时候，我们就需要对这些函数统计一个前缀和。因为，每当我们使用整除分块跳过一个区间的时候，其所对应的函数值也跳过了一个区间。所以此时，就需要乘上那一个区间的函数值。
• (当然，如果当出题人想要考考你的数论能力的话，这时就不是统计前缀和这么简单了。可能\[O(N)\]线筛都会TLE，那么我们就需要杜教筛了)
• (PS:关于杜教筛的内容，我没过多久就会写，那时候再填坑吧！)

整除分块

原文：https://www.cnblogs.com/My-snowing/p/10390340.html