浅谈整除分块

发表于 2021-06-06 分类于算法学习阅读次数： Valine：本文字数： 3k 阅读时长 ≈ 3 分钟

今天研究了下这玩意，查了几篇 blog，感觉脑子里乱七八糟的，于是自己写篇 blog 尝试总结一下。

前面的几个例子摘自这里，但是式子是自己手推的。

整除分块

考虑形如 $\sum_{i=1}^{n} \left\lfloor\frac{n}{i}\right\rfloor$ 这样的式子。

但是，使用整除分块能让计算这个东西的速度提升至 $O(\sqrt{n})$ 。

考虑 $n=10$ 的情况：

$i$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$\left\lfloor\frac{n}{i}\right\rfloor$	$10$	$5$	$3$	$2$	$2$	$1$	$1$	$1$	$1$	$1$

诶，怎么有这么多重复的 $\left\lfloor\frac{n}{i}\right\rfloor$ ？

事实上，随着 $i$ 的增长，这种重复项会越来越多。

于是我们只需要快速统计每种项出现了几次即可。

我们对于每个 $\left\lfloor\frac{n}{i}\right\rfloor$ 重复的段分开考虑。

$n=10$ 的情况中，这些段分别是 $[1,1],[2,2],[3,3],[4,5],[6,10]$ 。

我们可以扫一遍这个段的左端点，然后通过某种神奇方式快速知道这个段的右端点，扫下一个段的时候直接将左端点赋值为这个段的右端点 $+1$ 即可。

那么怎么知道左端点为 $l$ 的区间的右端点 $r$ 是什么呢？

根据我们定义的这种区间的性质：

\forall i\in[l,r],\left\lfloor\frac{n}{i}\right\rfloor=\left\lfloor\frac{n}{l}\right\rfloor

也就是说， $r$ 是最大的使 $\left\lfloor\frac{n}{i}\right\rfloor=\left\lfloor\frac{n}{l}\right\rfloor$ 的数 $i$ ，即

r=\max\left\{i,\left\lfloor\frac{n}{i}\right\rfloor=\left\lfloor\frac{n}{l}\right\rfloor\right\}

因此

r=\left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor

（这个可以手玩几组样例试试）

也就是说，我们知道 $l$ 之后就能快速知道对应的 $r$ 进行求解。

代码：

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

然后我们考虑更加一般性的问题，例如求

\sum_{i=1}^{n}\left\lfloor\frac{n}{ai+b}\right\rfloor

其中 $n,a,b$ 为给定常数。

我们还是按照老套路，考虑枚举一个 $l$ ，快速求解满足 $\left\lfloor\frac{n}{ai+b}\right\rfloor=\left\lfloor\frac{n}{al+b}\right\rfloor$ 的最大的 $i$ ，即为 $r$ 。

这个 $r$ 怎么求呢？

根据上一个例子，我们有

ar+b=\left\lfloor\frac{n}{\left\lfloor\frac{n}{al+b}\right\rfloor}\right\rfloor

因此

r=\left\lfloor\frac{\left\lfloor\frac{n}{\left\lfloor\frac{n}{al+b}\right\rfloor}\right\rfloor-b}{a}\right\rfloor

再考虑一个问题，求

\sum_{i=1}^{n}\left\lfloor\frac{n}{i^2}\right\rfloor

那么知道 $l$ 的情况下，可以得出

r^2=\left\lfloor\frac{n}{\left\lfloor\frac{n}{l^2}\right\rfloor}\right\rfloor

因此，

r=\left\lfloor\sqrt{\left\lfloor\frac{n}{\left\lfloor\frac{n}{l^2}\right\rfloor}\right\rfloor}\right\rfloor

先放一个 link。

\begin{aligned} G(n,k) &=\sum_{i=1}^{n}k\bmod i \\ &= \sum_{i=1}^{n}(k-i\left\lfloor\frac{k}{i}\right\rfloor)\\ &= nk-\sum_{i=1}^{n}i\left\lfloor\frac{k}{i}\right\rfloor \end{aligned}

因此，我们只需求

\sum_{i=1}^{n}i\left\lfloor\frac{k}{i}\right\rfloor

简单推一推，对于区间 $[l,r]$ ，答案是

\left\lfloor\frac{k}{l}\right\rfloor\cdot \frac{(l+r)(r-l+1)}{2}

代码：

int ans=n*k;
for(int l=1,r;l<=n;l=r+1) {
    if(k/l) r=min(k/(k/l),n);
    else r=n;
    ans-=(l+r)*(r-l+1)/2*(k/l);
}

其中，需要注意的细节有