数论分块是一种基础算法。他基于这样一个定理:
$\forall n,\lfloor\frac{n}{i}\rfloor$ 的取值最多只会有 $\mathcal{O}(\sqrt{n})$ 种。
我们可以找出对于每种取值 $j=\lfloor\frac{n}{i}\rfloor$ 所对应的 “连通块”。例如,对于 $n=10$,$j$ 的所有取值为 $10,5,3,2,2,1,1,1,1,1$。数论分块就可以帮助我们找到 $10$,$5$,$3$,$2,2$,$1,1,1,1,1$ 这 $5$ 个连通块。
算法的原理非常简单:每次只要把 $r$ 更新一下,计算答案以后,更新下一个连通块的左端点即可。
虽然算法显得简单,但是用途不菲。遇到一个数论计算问题和形如 $\frac{n}{i}$ 的式子时,我们通常会考虑:利用分块出来的连通块,计算这种取值对答案的贡献,然后快速计算出答案。比如说,让我们求出 $1\sim n$ 的约数个数之和。我们知道,一个约数 $k$ 对这个区间的贡献就是 $\frac{n}{k}$,便可用数论分块进行优化了!
接下来,我们看一下数论分块的模板:
LL res = 0;
int l = 1, r;
while (l <= n)
{
r = n / (n / l);
// TODO: 计算贡献
l = r + 1;
}
注意: 在 r = n / (n / l)
之后,当前取值为 $\lfloor\frac{n}{l}\rfloor$,取值所对的区间就是 $(l,r)$。