除法分块

使用场景

$$(1)\sum^n_{i=1}{\lfloor \frac{n}{i} \rfloor}\\ (2)\sum^n_{i=1}({\lfloor \frac{n}{i} \rfloor})^k\\ (3)\sum^n_{i=1}{\lfloor \frac{n}{i} \rfloor}{\lfloor \frac{m}{i} \rfloor}\\ (4)\sum^n_{i=1}({\lfloor \frac{n}{i} \rfloor-{\lfloor \frac{m}{i} \rfloor}})^k$$

形如上式的均可以使用分块除法来优化时间复杂度

效果

时间复杂度从$O(n)\rightarrow O(2\sqrt{n})$​

原理

下面对 (1) 式进行证明，其他式子可以同理推导得到

通过观察可以显然发现，在一段连续区间 $[l,r]$ 内，$\lfloor \frac{n}{i}\rfloor ，i\in[l,r]$ ，为了简化运算，把具有相同结果的区间分为一块，则问题便转化为了寻找每一块区间并计算其结果和。

l 的初值为 1 是显而易见的，下面对 r 的每一次取值进行证明。

• 本区间的值均为$\ \lfloor\frac{n}{l}\rfloor$
• 设 $\lfloor\frac{n}{l}\rfloor=x$,由题意可知需要寻找一个最大的 r，使得 $r*x<=n$ 成立
• 移项得$r<=\frac{n}{x}$
• 显而易见 r 的最大值为 $\lfloor\frac{n}{x}\rfloor$

代码

int l=1,r;
while(l<=n)
{
	r=n/(n/l);//当前的区间就是l~r，这个区间的值均为 n/l
	sum = sum + (r-l+1)*(n/l);
	l=r+1;
}

经典例题

UVA11526 H(n)（模板）

P2261 [CQOI2007]余数求和