在李煜东的书上做题,做到余数之和(https://www.luogu.com.cn/problem/P2261),发现这个是整除分块的模板题。。不是很会,学学。
看完上题,对于这个式子$$ \sum _{i=1}^{n} \lfloor \frac{n}{i} \rfloor $$ 一定不会陌生
这个式子在oi数论中十分常见,莫比乌斯反演等都会用到。求解这个式子,显然可以O(n)解决,但是遇到一些毒瘤出题人,毒瘤题(好像很常见),n可以上 $ 10^{????} $
那么显然不是要O(N)求解了。。而是要其他方法,比如--数论分块( $O(\sqrt n) $)(好像数据再打点这个也会die掉)
by 打表 我们可以发现
证明
1.打表
2.推导式子
证毕
$ \forall i \in [1,n],\lfloor \frac{n}{i} \rfloor$ 最多有\(2 \sqrt n\) 个取值。
当\(i \le \sqrt n\)时,i有\(\sqrt n\)种的选择,\(\lfloor \frac{n}{i} \rfloor\)也最多有\(\sqrt n\)个不同的值
当\(i>\sqrt n 时,\lfloor \frac{n}{i} \rfloor <\sqrt n\),所以\(\lfloor \frac{n}{i} \rfloor\)最多也只有\(\sqrt n\)的不同的值
所以,\(\forall i \in [1,n]\),\(\lfloor \frac{n}{i} \rfloor\)最多有2$\sqrt n $个不同的取值,即最多有\(2\sqrt n\)个块内值相等的块组成。
时间复杂度\(O(\sqrt n)\)
附上一个小模板
for(int l=1,r;l<=n;l=r+1)
{
r=n/(n/l);//int默认去除小数部分,就是只会向下取整
ans+=(r-l+1)*(n/l);
}