整除分块/数论分块

快速计算一群向下取整的和式，打包同时计算拥有相同的 $\lfloor\frac{n}{i}\rfloor$ 的分式，时间复杂度可以优化到 $O(\sqrt n)$

例如需要计算

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

依次写出拥有相同 $\lfloor\frac{n}{i}\rfloor$ 的分式

$$ \begin{array}{c|c|c|c|c|c|c|c|c|cc} i&1&2&3&4& 5& 6\ 7&8\ 9\ 10&11\cdots21 \\\hline \lfloor\frac{n}{i}\rfloor&21&10&7&5&4&3&2&1 \end{array} $$

分块存在两种性质：

  • 根据 $\lfloor\frac{n}{i}\rfloor$ 分块的数量 $\le2\lfloor \sqrt n\rfloor$

以 $\sqrt n$ 为分界线，$i\le \sqrt n$ 时，$\lfloor\frac{n}{i}\rfloor$ 有 $\lfloor\sqrt n\rfloor$ 种取值，$i> \sqrt n$ 时，$\lfloor\frac{n}{i}\rfloor$ 至多有 $\lfloor\sqrt n\rfloor$ 种取值

  • $i$ 所在分块的右端点为 $rfub$

$$ rfub=\lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor}\rfloor $$

设 $i$ 所在分块的 $\lfloor\frac{n}{i}\rfloor$ 为 $k$ ，则有以下推理

$$ k\le \frac{n}{i} \implies \frac{n}{k} \ge \frac{n}{\lfloor\frac{n}{i}\rfloor}\implies \lfloor \frac{n}{k}\rfloor \ge \lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor $$

又因为

$$ \lfloor \frac{n}{k}\rfloor \ge \lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor=\lfloor i\rfloor=i $$

那么 $i$ 所在分块的区间为

$$ \lfloor\frac{n}{\lfloor k_{i-1} \rfloor}\rfloor\le i \le \lfloor\frac{n}{\lfloor k_{i} \rfloor}\rfloor=\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor $$

综合以上两个性质，可以推广公式有

$$ \sum_{i=1}^n f(i)\lfloor\frac{n}{i}\rfloor $$

首先通过前缀和预处理 $f(i)$

$$ s(i)=\sum_{j=1}^i f(j) $$

那么答案就可以表示为

$$ \sum_{i=1}^n f(i)\lfloor\frac{n}{i}\rfloor=\sum_i [s(r)-s(l-1)]\cdot\lfloor\frac{n}{i}\rfloor $$

以计算 $\sum_{i=1}^{n} k\ \% \ i$ 为例

和式可以变形为

$$ \sum_{i=1}^{n} k\ \% \ i\implies \sum_{i=1}^{n} k-i*\lfloor\frac{k}{i}\rfloor=n*k-\sum_{i=1}^{n}i*\lfloor\frac{k}{i}\rfloor $$

代码实现如下：

long long n,k;
cin>>n>>k;
long long sum=n*k;
long long l,r;
for (l=1;l<=n;l=r+1){//计算分块左边界
    if (k/l==0) break;//如果l大于k，那么之后的项都为0，提前中断
    r=min(k/(k/l),n);//如果计算的右边界超出n，那么就到n为止
    sum-=(k/l)*(r-l+1)*(l+r)/2;//等差数列计算
}
cout<<sum;
return 0;