查看源代码：
min-denominator-in-a-range.md

---
title: 区间上的最小分母问题的两种解法
createTime: 2025/8/10
categories:
    - study
tags:
    - maths
---

:::note 问题
小数部分包含 $\overline{33550336}$ 的最小分母的分数是？（[@GooodPig](//gooodpig.pages.dev)）
:::

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

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

## 法 1

:::note 引理

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

---

**证明** 反证法，假设区间 $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)$ 亦为最小序，因此它有最优子结构.

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

### 代码

```cpp
#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

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

:::note 引理
**在不重的 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](https://www.luogu.com.cn/problem/P5179).

<!-- 考虑取加权平均，即 $\dfrac{m}{n} = \dfrac{33550336u + 33550337v}{10^8 \cdot (u+v)}$，不妨令 $u, v$ 互质.

由于 $\gcd(33550336u + 33550337v, u+v) = \gcd(u, v) = 1$，分母的 $u+v$ 不可能被约掉.  
因此，我们只能约掉 $2$ 或 $5$.

不妨固定约掉的因子，设 $2^x \cdot 5^y \mid 33550336(u+v)+v$，要求 $u+v$ 最小.  -->