数论分块

Summary

数论分块用于快速计算函数值与 n 除以 i 的向下取整值乘积的和式。这个取整值随 i 增大只有根号 n 种不同结果，且相同结果对应一段连续区间；已知左端点后，可以直接算出右端点。对每一段批量累加，即可把逐项求和降到 O(根号 n)。这种遍历方式也是杜教筛、莫比乌斯反演等数论求和的基础技巧。

参考资料

• 数论分块 - OI Wiki

简介

数论分块 用于快速计算形如 $\sum_{i=1}^n f(i)\lfloor n/i\rfloor$ 的和式。$\lfloor n/i\rfloor$ 随 $i$ 增大只取 $O(\sqrt n)$ 种不同值，且取同一值的 $i$ 构成一段连续区间 $[l,r]$，其右端点为 $r=\lfloor n/\lfloor n/l\rfloor\rfloor$。对每段批量累加即可在 $O(\sqrt n)$ 内完成。

实现

61 Bcpp

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

例题

洛谷 UVA11526 H(n)

给定 $T$ 次询问，每次询问一个正整数 $n$，求 $\sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor$。