关于数论分块做法的奇妙证明

yemuzhe · 2024-04-29 11:26:23 · 算法·理论

首先回顾一下数论分块（也即整除分块）的做法：

首先取 l = 1，然后不断取 r = \left \lfloor {n \over \left \lfloor {n \over l} \right \rfloor } \right \rfloor，计算 l \sim r 的贡献，再取新的 l ^ \prime = r + 1，重复操作，直到 l > n 为止。

对于不同的 [l, r]，至多只有 O (\sqrt n) 种，这个按根号分讨即可证明，这里不再赘述。

我们这里来讲一下做法的证明。

下面讲的是作者自认为很妙的一种证明，全由作者自行想出，如有雷同纯属巧合。

前置知识：如果 x \le y，则有 \lfloor x \rfloor \le \lfloor y \rfloor（易证）。

先放一个引理，很重要！！！

引理：对于任意的正整数 n, x 满足 x \le n，有：

\left \lfloor {n \over \left \lfloor {n \over x} \right \rfloor } \right \rfloor \ge x

证明：

\because \left \lfloor {n \over x} \right \rfloor \le {n \over x}

因为对于正数而言，分母越小分数值越大，所以：

\therefore {n \over \left \lfloor {n \over x} \right \rfloor } \ge {n \over {n \over x}} = x

注意 x 是整数，得到：

\therefore \left \lfloor {n \over \left \lfloor {n \over x} \right \rfloor } \right \rfloor \ge \lfloor x \rfloor = x

证毕。

接下来我们尝试证明以下命题：

对于第一个命题，可以这样证明：

我们先把 r 用 l 表示出来：

然后得出：

注意观察这个式子。我们如果把底下的 \left \lfloor {n \over \left \lfloor {n \over l} \right \rfloor } \right \rfloor 这一坨东西用引理换掉，得到：

因为分母越小分数值越大，有：

套上取整符号，得：

即

如果我们把原来式子最下面的 \left \lfloor {n \over l} \right \rfloor 看成一个整体（x）再套引理，可得：

即

结合 (1)(2) 得 \left \lfloor {n \over l} \right \rfloor = \left \lfloor {n \over r} \right \rfloor。

这样我们就证出了第一个命题。

关于第二个命题，首先有 \left \lfloor {n \over l} \right \rfloor \ge \left \lfloor {n \over r + 1} \right \rfloor。

考虑反证法，假设 \left \lfloor {n \over l} \right \rfloor = \left \lfloor {n \over r + 1} \right \rfloor。

那么有

又由引理得

矛盾！故 \left \lfloor {n \over l} \right \rfloor > \left \lfloor {n \over r + 1} \right \rfloor。

我们由一个引理，巧妙证明了以上命题，证毕。