数论分块

文章借用: 浅谈数论分块 - 洛谷专栏 (luogu.com)

求 $\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor$，其中 $n$ 为常数。

为了方便我们的研究，我使用绘图软件画出了 $f(x) =\frac{7}{x}(1\leq x\leq 7)$ 的图像，也就是一种反比例函数的图像。

 因为求的值是向下取整的，显然函数 $f(x)$ 在 $[1,7]$ 区间内是单调递减的，我们不妨把 $\lfloor \frac n i\rfloor$ 取值相同的段取出来

 图像被分割为了 $7$ 个大块，但取值范围包含整数的只有 $4$ 个，那么如果我们可以把这些包含整数的块取出来，一次性得出一个块的答案，把整块对答案的贡献加上即可。

如果要实现整块一起统计，我们需要求出每一块的块头 $l$ 和块尾 $r$，则：

$$\sum_{i=1}^n \lfloor \frac n i \rfloor = \sum _{(l,r)} (r-l+1) \lfloor \frac n l \rfloor$$

给出一个结论： 对于整数 $i$，其所在块的右端点为 $\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor$，在此给出两种证明方式：

1. 代数法

首先我们要证明 $\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor$ 与 $i$ 在同一块，也就是：$$\lfloor\frac{n}{\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor}\rfloor= \lfloor\frac{n}{i}\rfloor$$

易证：

$$ \lfloor x\rfloor \leq x$$

$$x \le y\to \lfloor x\rfloor \le \lfloor y\rfloor$$

$$x \ge y\to \lfloor x\rfloor \ge \lfloor y\rfloor$$

则:

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

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

所以：

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

我们还要证明：

$$i \le \lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor$$

也就是 $\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor$ 是这个块内最大的，即为块的右端点，这个很好证明：

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

这样我们就以代数方式证明了结论，如果看不懂还有几何的。

2. 几何法

$\frac{n}{\lfloor \frac n i \rfloor}$ 的意义即为直线 $y=\lfloor \frac n i \rfloor$ 与直线 $y=\frac n x$ 的交点的横坐标，取整后就是这个交点左侧第一个整数横坐标，如图：

 $l_1$ 为直线 $y = \lfloor \frac n i \rfloor $，$l_2$ 为直线 $y=\lfloor \frac n i \rfloor +1$，我们不妨设 $l1$ 与直线 $y=\frac n x$ 的交点为 $P$，$l_2$ 与直线 $y=\frac n x$ 的交点为 $Q$，则：

$$\forall x_{Q} < x \le x_{p}, \lfloor\frac n x\rfloor = \lfloor\frac n i\rfloor$$

那么 $x_{P}$ 也就是 $\frac{n}{\lfloor \frac n i \rfloor}$ 左侧的第一个整点 $\lfloor \frac{n}{\lfloor \frac n i \rfloor}\rfloor$ 即为这些点里的最大整数点。

证毕.

复杂度证明: 

当 $x \in [1, \lfloor\sqrt n\rfloor]$ 这个区间，最多有 $\lfloor\sqrt n\rfloor$ 种取值。

当 $x \in (\lfloor\sqrt n\rfloor,n]$ 这个区间，$\lfloor\frac n x\rfloor$ 显然只能取到 $[1, \lfloor\sqrt n\rfloor)$这个区间，最多有 $\lfloor\sqrt n\rfloor$ 种取值。

则至多有 $2\lfloor\sqrt n\rfloor$ 种取值，复杂度为 $O(\sqrt n)$。

代码: