问题

小数部分包含 $\overline{33550336}$ 的最小分母的分数是？（@GooodPig）

贪心地，我们将 $33550336$ 固定在小数部分开头，这是因为 $10^k \cdot q$ 的分母总是不大于 $q$.

不妨令整数部分为 $0$，于是 $0.33550336 \le \dfrac{m}{n} < 0.33550337$.

法 1

引理

在一个区间内字典序最小的分数与反字典序最小的分数为同一个.

---

证明 反证法，假设区间 $D$ 内字典序最小的分数为 $\frac{a}{b}$，反字典序最小的分数为 $\frac{c}{d}$，且 $\frac{a}{b} \ne \frac{c}{d}$.
由字典序与反字典序的定义，$a < c, d < b$.
注：不能取等，否则违反假设，其中一个并非字典序/反字典序最小）

则 $\frac{a}{d} \in (\frac{a}{b}, \frac{c}{d}) \subseteq D$ 比 $\frac{a}{b}, \frac{c}{d}$ 字典序与反字典序都要小. 矛盾.

不妨将在一个区间内字典序/反字典序最小的分数称为最小序分数.

原命题等价于：

求最小序的分数 $\frac{m}{n} \in [\frac{a}{b}, \frac{c}{d})$.

令 $n=qm+r$，则

$$\frac{d-qc}{c} < \frac{r}{m} \le \frac{b-qa}{a}.$$

这是一个更小规模的子问题，由于若 $(n, r)$ 为最小序，$(qm+r, r) = (n, r)$ 亦为最小序，因此它有最优子结构.

注

$q$ 可以任取，根据辗转相除的原理可知等价性. 然而取最大的 $q = \lfloor d/c \rfloor$ 有助于加快求解速度.

代码

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct frac {
    int p, q;
};

frac find(frac l, frac r, bool cl, bool cr) {
    if ((cl? l.p <= l.q: l.p < l.q) &&
        (cr? r.p >= r.q: r.p > r.q)) {
        return {1, 1};
    }
    
    int k = r.q / r.p;
    frac f = find({r.q - k * r.p, r.p},
                  {l.q - k * l.p, l.p},
                  cr, cl);
    return {f.q, f.p + k * f.q};
}

signed main() {
    while (true) {
        int n, b, x=0, div=1;
        cin >> n >> b;
        for (int i=1; i<=n; i++) {
            int s;
            cin >> s;
            x = x * b + s;
            div *= b;
        }
        
        frac ans = find({x, div}, {x+1, div}, (x % b) != 0, 0);
        printf("%lld/%lld\n", ans.p, ans.q);
    }
    
    return 0;
}

法 2

注意

该方法在处理开区间的时候需要一个特判，对应的程序较为繁琐。

引理

在不重的 BST（二叉搜索树）$T$ 中，两节点 $l$ 和 $r$ 的 LCA（最近公共祖先）是区间 $[l,r]$ 中深度最小的节点.

---

证明：设 $\operatorname{LCA}(l, r) = x$，由 BST 的性质可得：

1. $x \in [l, r]$；
2. 所有满足 $a \in [l, r]$ 的节点 $a$ 必然位于 $x$ 的子树中，深度比 $x$ 大.

由于 Stern–Brocot 树有 BST 性质，且祖先的分母必定比后代小，答案即为 Stern–Brocot 树上 $0.33550336, 0.33550337$ 的 LCA.

根据熟知结论，一个分数的连分数表示去掉末尾的 $1$ 之后编码了这个分数在 Stern–Brocot 树上的索引.

由

$$\begin{aligned} 0.33550336 &= [0, 2, 1, 50, 1, 1, 6, 2, 4, 3, 4, 1], \\ 0.33550337 &= [0, 2, 1, 50, 1, 1, 6, 2, 40, 1, 4, 1, 91, 1] \end{aligned}$$

可得答案为

$$[0, 2, 1, 50, 1, 1, 6, 2, 4, 1] = \frac{7885}{23502}.$$

关联 OI 题目：Luogu P5179 Fraction.