祝 jiazhichen844 和 Olddrivertree 两位大神百年好合！

违规用户名1425622 · 2025-03-02 22:28:22 · 题解

不是这么良心的题咋没有题解啊？那我就先写一篇抢个一血吧。

一、什么是 Stern–Brocot tree？

Stern–Brocot tree（也可以叫 SBtree）是一种可以维护所有既约分数（分子分母互质）的树形结构，长成这样：

（图源来自 oi-wiki，侵删）

那么这颗树是怎么建成的呢？

事实上，我们可以按照如下方式构建一棵 Stern–Brocot tree。

• 我们设一对分数 (\frac{a}{b},\frac{c}{d}) 表示一棵下界为 \frac{a}{b}，上界为 \frac{c}{d} 的 Stern–Brocot tree，那么其根的左儿子为 (\frac{a}{b},\frac{a+c}{b+d})，右儿子为 (\frac{a+c}{b+d},\frac{c}{d})，根代表的分数即为 \frac{a+c}{b+d}。

那么原图的含义就很明显了，就是一棵以 (\frac{0}{1},\frac{1}{0}) 生成出来的 Stern–Brocot tree（在这里，\frac{0}{1} 表示 0，\frac{1}{0} 表示 +\infty）。

那么这么奇怪的定义方法得到的树有什么性质吗？

二、这种东西有什么性质呢？

实际上，Stern–Brocot tree 有着很多非常良好的性质，这也使得它成为了维护既约分数的最常用方法，我们依次来看。

• 最简性：Stern–Brocot tree 上的所有分数都为既约分数。
• 单调性：Stern–Brocot tree 的中序遍历单调递增。
• 完整性：Stern–Brocot tree 不重不漏的包含了所有既约分数。
• 有限性：Stern–Brocot tree 上的所有分子和分母有限的既约分数的深度也有限，具体的，设 \operatorname{dep}(\frac{a}{b}) 表示分数 \frac{a}{b} 的深度，则有 \operatorname{dep}(\frac{a}{b}) \le a+b。

如果不想看详细的数学证明可以跳过，因为只要知道结论即使不知道证明也可以看懂下面的内容，但是看了证明会加深你对 Stern–Brocot tree 的理解，下面将逐个证明这些结论。

part.1 最简性

问题相当于保证 \gcd(a,b)=1,\gcd(c,d)=1，要求证明 \gcd(a+b,c+d)=1。

由于裴蜀定理，则我们只需要找到一组整数 x,y 满足 (a+c)x+(b+d)y=1 就行了。

我们令 x=b,y=-a，则相当于要求证 bc-ad=1。

引理 1.1：对于在 Stern–Brocot tree 种属于同一层的相邻既约分数 \frac{a}{b} 和 \frac{c}{d}，有 bc-ad=1。

考虑数学归纳，如果上一层的两个分数为 \frac{a}{b} 和 \frac{c}{d}，考察其生成出来的分数 \frac{a+c}{b+d}，则我们有 b(a+c)-a(b+d)=(b+d)c-(a+c)d=1，证明完毕。

由引理 1.1 易得最简性成立。

part.2 单调性

由 Stern–Brocot tree 的生成方式易得命题等价于 \frac{a}{b} < \frac{a+c}{b+d} < \frac{c}{d}，容易通过不等式证明。

part.3 完整性

这里我认为 oi-wiki 上利用有限性给的证明是不严谨的，因为有限性的成立建立在所有分数均可表示的基础上，因此我会给出一个不需要有限性的证法。

考虑将 Stern–Brocot tree 上的所有分数看作向量。

那么对于一个向量 (x,y) 满足 \gcd(x,y)=1，设离他最近且在它与原点连线的上方的整点叫 (x_0,y_0)，则我们可以得到 y_0x-x_0y=1，证明利用裴蜀定理是容易的，则可以得到 (x-x_0,y-y_0) 为在它与原点连线的下方的距离最短的点，那么如果 (x,y) 能生成等价于 (x_0,y_0) 和 (x-x_0,y-y_0) 能生成，容易通过数学归纳法求证。

part.4 有限性

考虑 Stern–Brocot tree 的生成方式，不妨设当前的子树为 (\frac{a}{b},\frac{c}{d})，考虑每一个 \frac{a}{b}<\frac{p}{q}<\frac{c}{d}，

那么我们显然有 bp-aq \ge 1,cq-dp \ge 1。

将两式分别乘以 c+d 和 a+b 后加起来得到 p+q \ge a+b+c+d，每次递归右侧至少增加 1，所以 \operatorname{dep}(\frac{p}{q}) \le p+q。

三、这个东西有什么用呢？

好吧其实这个东西没什么用。

当我们要求与有理数相关的问题时，Stern–Brocot tree 就是一个很好用的工具，比如其最常见的应用：最佳有理逼近。

最佳有理逼近

问题形如：给定一个数 x，要求出一个距离 x 最近且满足某些条件的既约分数 \frac{p}{q}，并且这个“某些条件”关于分数的大小是单调的（也就是说满足二分条件）。

关于这个问题 oi-wiki 上已经做了详细的说明，具体思路就是我们维护每次要是要走向左儿子还是右儿子，并且求出走向左儿子的次数和右儿子的次数，当我们知道 x 的时候我们查找的复杂度是只有 \log 的，因为向左走一次和向右走一次至少会有一个分数的分子和分母翻倍。

但是我们不知道 x 或者“某些条件”比较复杂不能直接求出来走的次数呢？这个时候我们就可以倍增了，但是这个时候我们最坏情况会检查 \log^2 次，难道我们真的没有办法只检查 O(\log) 次吗，不，其实是有的，考虑下面的方法：

• 对于每次向左或右跳的过程，先倍增求出跳 2^c 步还能使条件成立的最大的 c，之后从 2^c 开始倍增求出精确的步数。

你可能会说，这个东西还要倍增两遍，难道不是比我 \log^2 还慢吗？不是的，设答案为 \frac{p}{q}，实际上可以证明每次的倍增过程不超过 8\log(u+v) 次，证明可以看这篇。

四、一些需要用到的题

P1797【模板】Stern-Brocot 树

第一、二、五个操作易做，考虑第三和四个，发现第三个操作只需要求出来两个分数的操作路径的最长相等前缀即可，第四个操作类似。

P8058 [BalkanOI 2003] Farey 序列

很经典的最佳有理逼近问题，check 可以使用类欧和狄利克雷求和搞定。

AT_abc333_g [ABC333G] Nearest Fraction

盐都不盐了，最佳有理逼近板子。