整除分块学习笔记

Posted on | In |
Words count in article: 578 | Reading time ≈ 2

虽然说不是什么很难的东西就是了，不过好像在莫反中会有用到，就先来讲一下。

整除分块学习笔记

1.提出问题

这里给出一个相当典型的例子。

求以下式子的结果（ $\lfloor n \rfloor$ 表示对 $n$ 下取整）：

很显然当 $n$ 并不大的时候可以思博 $O(n)$ 的解决，但如果 $n$ 比较大了呢？

2.整除分块

由以上问题我们提出整除分块这个概念。

很显然我们可以知道在我们 $O(n)$ 做的时候会很多次的计算相同的值，然后我们冷静分析暴力打表一波会发现有以下性质：

  1. $\lfloor \frac{n}{i} \rfloor$ 最多只有 $2\sqrt{n}$ 种取值，理由很简单：对于 $i \leq \sqrt{n}$ ，显然只有 $\sqrt{n}$ 种，对于 $i > \sqrt{n}$ 的情况，显然 $\frac{n}{i} < \sqrt{n}$ ，于是也只有 $\sqrt{n}$ 种。
  2. 假如 $\lfloor \frac{n}{j} \rfloor = \lfloor \frac{n}{i} \rfloor$ ，则 $j$ 的最大值为 $\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor$ 。

证明如下：

设 $\lfloor \frac{n}{i} \rfloor = k$ ，则有 $ki + p = n\ \ (\ p\in[1,i)\ )$ ，我们再假设 $\lfloor \frac{n}{i + d} \rfloor = k$ ，于是有 $k(i + d) + q = n\ \ (\ q\in[1, i + d)\ )$ ，两式相减可以得到 $q = p - kd$ ，则有 $d_{max} = \lfloor \frac{p}{k} \rfloor$ ，于是：

此时再来谈到整除分块，已知一个块的左端点为 $l$ ，我们就可以根据以上性质求出右端点 $r = \lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor$ ，然后统计答案的时候加上 $(r - l + 1) \times \lfloor \frac{n}{l} \rfloor$ 就可以了，然后由于性质1，我们可以知道块数最多为 $2\sqrt{n}$ ，所以复杂度为 $O{\sqrt{n}}$ ，可以通过 $n​$ 较大的数据Da☆Ze。

以下放出代码：

1
2
3
4
5
for (ri l = 1, r; l <= r; l = r + 1)
{
    r = n / (n / l);
    ans += (r - l  + 1) * (n / l);
}
0%