数论分块学习笔记

性质

数论分块用于快速计算含有除法向下取整的和式，即形如 \(\sum_{i=1}^nf(i)g(\lfloor\frac{n}{i}\rfloor)\) 的式子。当预处理出 \(f\) 的前缀和时，数论分块可以在 \(O(\sqrt{n})\) 的时间复杂度下计算上述和式的值。

求解

引理 \(1\)：

\(\forall a,b,c\in\mathbb{z},\lfloor\frac{a}{bc}\rfloor=\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor\)

证明：

不妨设 \(a=kb+r(0\le r<b)\)，那么 \(\lfloor\frac{a}{b}\rfloor=k\)。

所以有 \(\lfloor\frac{a}{bc}\rfloor=\lfloor\frac{\frac{a}{b}}{c}\rfloor=\lfloor\frac{k+\frac{r}{b}}{c}\rfloor\)。

因为 \(k\) 是整数，\(r<b\)，所以 \(\lfloor\frac{k+\frac{r}{b}}{c}\rfloor=\lfloor\frac{k}{c}\rfloor=\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor\)。

即 \(\lfloor\frac{a}{bc}\rfloor=\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor\)。

引理 \(2\)：

\(\forall n\in\mathbb{N}_+,|\{\lfloor\frac{n}{d}\rfloor|d\in\mathbb{N}_+,d\le n\}|\le \lfloor2\sqrt{n}\rfloor\)​。

证明：

对于 \(d\le\lfloor\sqrt{n}\rfloor\)，有 \(\lfloor\frac{n}{d}\rfloor\) 最多有 \(\lfloor\sqrt{n}\rfloor\) 种取值，因为 \(d\) 最多有 \(\lfloor\sqrt{n}\rfloor\) 种取值。

对于 \(d>\lfloor\sqrt{n}\rfloor\)，有 \(\lfloor\frac{n}{d}\rfloor\) 最多有 \(\lfloor\sqrt{n}\rfloor\) 种取值，因为 \(\lfloor\frac{n}{d}\rfloor\le\lfloor\sqrt{n}\rfloor\) 。

即 \(\forall n\in\mathbb{N}_+,|\{\lfloor\frac{n}{d}\rfloor|d\in\mathbb{N}_+,d\le n\}|\le \lfloor2\sqrt{n}\rfloor\)。

结论：

对于两个整数 \(n,i\)，满足 \(\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{j}\rfloor,i\le j\le n\) 的最大的 \(j\) 值为 \(\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor\)。

证明：

令 \(k=\lfloor\frac{n}{i}\rfloor\)，易知 \(k\le\frac{n}{i}\)。

所以有 \(\lfloor\frac{n}{k}\rfloor\ge\lfloor\frac{n}{\frac{n}{i}}\rfloor=\lfloor i\rfloor=i\)。

因为 \(j\) 改变时 \(k\) 为定值，所以 \(j\le\lfloor\frac{n}{k}\rfloor=\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor\)。

如此可以得到以下几个性质：

• \(\lfloor\frac{n}{i}\rfloor\) 的值的个数不超过 \(\lfloor2\sqrt{n}\rfloor\)，也就是说，枚举 \(\lfloor\frac{n}{i}\rfloor\) 的时间复杂度是 \(O(\sqrt{n})\)。
• 通过 \(\lfloor\frac{n}{i}\rfloor\)，假设使得这个值不变的区间的范围是 \([l,r]\)，那么可以在 \(O(1)\) 时间内求解出该区间的最右边，并且 \(r+1\) 一定是下一个区间的最左边。

那么就有以下的代码思路：

考虑当 \(\lfloor\frac{n}{i}\rfloor\) 的值不变时，对于这些项的求和 \(\sum_{i=l}^rf(i)g(\lfloor\frac{n}{i}\rfloor)=g(\lfloor\frac{n}{i}\rfloor)\sum_{i=l}^rf(i)\)，显然后半部分可以利用前缀和求出，只需要求出前半部分的值即可。

从 \(l=1\) 开始枚举，每次考虑区间 \([l,\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor]\) 对答案的贡献，也就是 \(g(\lfloor\frac{n}{l}\rfloor)\sum_{i=l}^{\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor}f(i)\)。后半部分利用前缀和快速求解，前半部分直接计算即可。

最后令 \(l=\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor+1\)，作为下一个枚举区间的左端点。

显然这样的复杂度是 \(O(\sqrt{n})\) 的。

代码

for(int l=1,r;l<=n;l=r+1){
	r=n/(n/l);
    ans+=(f[r]-f[l-1])*g[n/l];
}