整除分块学习笔记

什么是整除分块

通俗的讲，是一种能用 $O(\sqrt{n})$ 的时间复杂度解决一些含有 $\left \lfloor \frac{n}{i} \right \rfloor $ 的式子（下取整）

整除分块的原理

如图，当 $x >4$时，我们发现它是连续的，于是我们可以尝试找出块长的规律，即可连续计算。

至于规律嘛：（摘自这里）

数论分块结论

对于常数 $n$ ，使得式子 $ \frac{n}{i}=\frac{n}{j}$

成立的最大的满足 $i\leq j \leq n $ 的 $j$ 的值为$\left \lfloor \frac{n}{\left \lfloor \frac{n}{i} \right \rfloor } \right \rfloor $。即值 所在的块的右端点为 $\left \lfloor \frac{n}{\left \lfloor \frac{n}{i} \right \rfloor } \right \rfloor $

我也不知道为什么这是怎么搞出来的，人类智慧是无穷的

代码大概是这样：

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

例题

UVA11526

板子。

P2261

$$\sum_{i=1}^{n} k \bmod{i} = \sum_{i=1}^{n} k-\left \lfloor \frac{k}{i} \right \rfloor \times i$$

结束。