数论分块

参考资料

• 数论分块 - 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$。