整除分块

整除分块

可以用到整除分块的形式,大致是这样的:

\[\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor \]

这种式子因为特殊的要求,通常是要求 \(O(\sqrt{n})\) 的复杂度去算。

对于每一个 \(\lfloor\frac{n}{i}\rfloor\) 我们可以通过打表(或理性的证明)可以发现:

有许多 \(\lfloor\frac{n}{i}\rfloor\)的值是一样的,而且它们呈一个块状分布.

再通过打表之类的各种方法,我们惊喜的发现对于每一个值相同的块,它的最后一个数就是 \(n/(n/i)\)。得出这个结论后,我们就可以做的 \(O(\sqrt{n})\)处理了。

代码:

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

拓展:

有时候,可能推出来的式子不一定就是一个很裸的整除分块,可能会与某些积性函数相乘,如:\(μ,φ......\) 这时候,我们就需要对这些函数统计一个前缀和。

因为,每当我们使用整除分块跳过一个区间的时候,其所对应的函数值也跳过了一个区间。所以此时,就需要乘上那一个区间的函数值。

上一篇:Elasticsearch 5.4.3实战--Java API调用:搜索建议


下一篇:P3327 [SDOI2015]约数个数和 题解