分数树 Stern-Brocot Tree

从两个边界开始Starting from Two Bounds#

取两个“分数”作为初始边界：

其中 严格来说不是分数，我们在这里把它理解为 的一个占位符（这样写纯属为了方便叙述，程序中谁也不会去真的拿它当分母）。

每一轮迭代中，我们取出序列里所有相邻的两个分数 与 ，在它们中间插入中位分数Mediant：

第一轮之后序列变成：

第二轮：

第三轮：

如果把这些“插入”看成树上的节点，就得到了分数树的结构。以 为根节点，左子树由 与 之间的所有分数递归生成，右子树由 与 之间的分数递归生成，便得到：

三条基本性质Three Basic Properties#

这个构造之所以成立，靠的是下面三条性质（证明在 OI Wiki 上很详细，这里只讲结论）：

1. 单调性：每一轮迭代结束后，序列都是严格递增的。
2. 最简性：每一轮插入的分数都是既约分数。
3. 完全性：任意一个非负既约分数 ，都会在某一轮恰好出现一次。

单调性与最简性的证明是同一套路的双重归纳。先定义两个分数 、 的行列式Determinant：

那么初始的两项 与 之间满足

也就是说 。这个性质在插入中位分数时是可以传递的：对相邻三项 ，有

于是“相邻两项的行列式绝对值为 ”在每一步迭代后都成立。而由

立刻得到 ，即每一项都是既约分数——最简性就保住了。 这一项需要特殊处理（分母为 时上述约定照旧成立），这就是为什么它只是一个占位符。

为什么它是二叉搜索树Why Is It a Binary Search Tree#

分数树和 的对应关系非常直白：

• 左子树的所有分数都小于当前节点，右子树都大于当前节点；
• 当前节点总等于左右两条边界的中位分数；
• 中序遍历得到的就是整个分数序列，与前面逐轮构造出来的序列完全一致。

因此在树上做二分查找是天然成立的，这就是后文所有算法的出发点。

结构定义Structure Definition#

分数树不同于前面三棵树的地方在于，它几乎不需要显式建树。绝大多数题目只需要维护“当前所在区间的两个边界”以及“当前访问到的节点”，三个分数即可完整描述一次搜索，属于是数据结构里罕见的“用三个变量就能跑”的选手。为了统一写法，我们还是给分数定义一个结构体：

1
struct Frac {
2
  long long u, v;  // Numerator and denominator
3
};

其中 v 始终为正。由于 作为上边界参与运算，程序里所有涉及它的地方都要单独处理，不能真的去拿它做除法或取模——下文所有代码都遵守这一约定。

分数比较Fraction Comparison#

一切操作的基础是两个分数的大小比较。直接除肯定不行（精度不够，而且 直接就炸了），正确做法是交叉相乘再比较：

实现时为了避免乘法溢出，统一强制转换成 __int128 再做减法：

1
// Compare a/b with c/d, return 1 if greater, -1 if smaller, 0 if equal
2
int compare(long long a, long long b, long long c, long long d) {
3
  __int128 x = (__int128)a * d - (__int128)c * b;
4
  if (x > 0) return 1;
5
  if (x < 0) return -1;
6
  return 0;
7
}

树上遍历Tree Traversal#

分数树虽然不用真的建树，但遍历是必要的。最典型的用法是：输出所有分母不超过 的既约分数（洛谷 P1458）。做法就是一次中序遍历，只不过“剪枝”的门槛换成了分母大小：

1
int n;
2

3
// Output every reduced fraction strictly inside (au/av, bu/bv) with denominator <= n
4
void dfs(int au, int av, int bu, int bv) {
5
  int mu = au + bu, mv = av + bv;  // Mediant of the two bounds
6
  if (mv > n) return;        // Denominator exceeds n, prune the whole subtree
7
  dfs(au, av, mu, mv);      // Walk into the left subtree
8
  printf("%d/%d\n", mu, mv);    // Visit the current node
9
  dfs(mu, mv, bu, bv);      // Walk into the right subtree
10
}

调用时以 与 为初始边界（两端的 、 单独输出），就能按递增顺序得到全部答案。因为中序遍历的顺序就是分数递增的顺序，所以代码里完全不需要排序——这就是分数树最优雅的地方。

朴素查找Naive Search#

有了 的性质，查找一个给定分数 的思路是显而易见的：从根 出发，比当前节点小就往左，大就往右，一路走到底。

用“边界 + 节点”的写法描述就是：初始边界为 与 ，每步取中位分数 与目标比较，据此把左边界或右边界替换成中位分数，直到中位分数恰好等于目标。

1
// Find p/q in the tree, return the number of steps to reach it
2
int search(long long p, long long q) {
3
  long long au = 0, bu = 1;  // Lower bound
4
  long long av = 1, bv = 0;  // Upper bound
5
  int step = 0;
6
  while (true) {
7
    long long cu = au + av, cv = bu + bv;  // Mediant, the node we are visiting
8
    if (compare(cu, cv, p, q) == 0) return step;
9
    if (compare(cu, cv, p, q) < 0) {
10
      au = cu, bu = cv;          // Target is bigger, move the lower bound up
11
    } else {
12
      av = cu, bv = cv;          // Target is smaller, move the upper bound down
13
    }
14
    step++;
15
  }
16
  return -1;
17
}

这个做法的复杂度是 的——最坏情况是查找 ，从根 开始要连续向左走 步才能到它。对于 还能勉强接受，再大就不行了。

跳跃优化Jump Optimization#

观察一下就会发现，朴素查找的慢不在于走了多远，而在于连续做了多少次同方向的无效判断。查找 时，从 出发要连续向左走 步，而这 步里每一步做的事情其实是同一件。

于是很自然地想到：连续同向的若干步，能不能一次走完？

答案是肯定的。设当前所在节点为 ，左、右边界分别为 、。若下一步要向右跳 步，那么走完之后右侧界会变成

令它“刚好越过”目标分数，即可解出 ：

因此最小的合法 就是 。向左跳的推导完全对称，只需要把分子分母的角色对调。

而一旦“跳一次”成功越过目标，上一步所在的位置就一定是我们想要的答案——因为分数树的深度随分母单调增加，第一次进入目标区间的那一层就是所有答案中深度最浅的一层。这个性质在下一节会被用到。

区间查找Interval Query#

真正有意思的问题往往是：给定一个区间 ，求其中分母最小的既约分数。

这正好是刚才那条性质的直接应用——分母最小的分数，就是分数树中第一个落进该区间的节点，也就是深度最浅的那个节点。于是算法就变成了：一边向下走，一边判断当前所在区间的中位分数是否已经进入目标区间，进去了就立即停下。

1
// Find the fraction with the minimum denominator strictly inside (A/B, C/D)
2
void solve(long long A, long long B, long long C, long long D) {
3
  long long lu = 0, lv = 1;  // Lower bound 0/1
4
  long long ru = 1, rv = 0;  // Upper bound 1/0
5
  long long cu = 1, cv = 1;  // Node we are visiting, initially the root 1/1
6
  while (true) {
7
    // Step 1: has the current node fallen into the target interval?
8
    if (compare(cu, cv, A, B) > 0 && compare(cu, cv, C, D) < 0) break;
9
    // Step 2: otherwise move towards the interval
10
    if (compare(cu, cv, A, B) <= 0) {
11
      // Current node <= A/B, so we have to go right. Work out the jump length first
12
      long long t = (long long)(((__int128)A * cv - (__int128)cu * B) / ((__int128)ru * B - (__int128)A * rv));
13
      if (t < 1) t = 1;
14
      lu = cu + (t - 1) * ru;  // The last node not exceeding A/B becomes the lower bound
15
      lv = cv + (t - 1) * rv;
16
    } else {
17
      // Current node >= C/D, so we have to go left
18
      long long t = (long long)(((__int128)cu * D - (__int128)C * cv) / ((__int128)C * lv - (__int128)lu * D));
19
      if (t < 1) t = 1;
20
      ru = cu + (t - 1) * lu;  // The last node not going below C/D becomes the upper bound
21
      rv = cv + (t - 1) * lv;
22
    }
23
    cu = lu + ru;        // The new node is always the mediant of the two bounds
24
    cv = lv + rv;
25
  }
26
  printf("%lld/%lld\n", cu, cv);
27
}

这段代码里有几个点需要单独交代：

1. t = 1 的兜底不能省。当 t 算出来是 时，意味着当前节点已经“贴”在边界上，此时至少要走一步，否则 lu/lv 不会更新，循环就会原地打转——这是手写跳跃时最容易踩的坑。
2. lu 的取值是 cu + (t - 1) * ru 而不是 cu + t * ru。因为第 步正好跨过目标，所以“最后一个没越过目标的节点”是第 步的位置，它才应该是新的边界。
3. 中途乘法的溢出。A * cv 这类的量在数值上可能达到 ，必须用 __int128 计算；而 本身通常不大，转回 long long 是安全的。这也是为什么整个算法强烈建议在 64 位环境下配合 __int128 使用。

洛谷 P1458 [USACO2.1] 顺序的分数 Ordered Fractions#

题目地址：P1458

题目难度：普及-

输入一个自然数 ，对于一个最简分数 （分子和分母互质的分数），满足 ，请找出所有满足条件的分数。

这有一个例子，当 时，所有解为：

给定一个自然数 ，请编程按分数值递增的顺序输出所有解。

输入格式：

单独的一行一个自然数

输出格式：

每个分数单独占一行，按照大小次序排列

数据范围：

对于 的数据，。

这就是标准的“分母不超过 的分数遍历”，直接把上面那个 dfs 抄下来就能过。唯一需要注意的是首尾两个数 与 要单独输出，因为它们是边界而不是中位分数。

完整代码：

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

4
int n;
5

6
void dfs(int au, int av, int bu, int bv) {
7
  int mu = au + bu, mv = av + bv;
8
  if (mv > n) return;
9
  dfs(au, av, mu, mv);
10
  printf("%d/%d\n", mu, mv);
11
  dfs(mu, mv, bu, bv);
12
}
13

14
int main() {
15
  scanf("%d", &n);
16
  printf("0/1\n");
17
  dfs(0, 1, 1, 1);
18
  printf("1/1\n");
19
  return 0;
20
}

由于 ，分母沿递归单调递增，递归深度只有 量级，完全不用担心爆栈。复杂度是输出量级别的 ，而 ，对 来说就是前面提过的七千八百多个分数，跑起来非常轻松。

顺便一提，这道题用普通的“枚举 + 排序”也能过，但既然是分数树专题，总得给分数树一点面子。

AtCoder ABC408 G - A/B < p/q < C/D#

题目地址：ABC408 G

题目难度：省选/NOI-

给定满足 的正整数 ，求最小的正整数 ，使得存在正整数 满足：

共 组数据。

输入格式：

第一行一个整数 ，接下来 行每行四个整数 。

输出格式：

输出 行，每行一个整数表示答案。

数据范围：

，，保证 。

正儿八经的区间查找模板题。题意就是求区间内分母最小的分数，而且区间端点本身可能不是既约分数（题目没有保证），但这并不影响算法——分数树上只有既约分数，我们的比较全程使用交叉相乘，不做任何约分，因此结果天然既约。

直接套用上面的 solve() 即可，只需注意读入用 long long、中间运算用 __int128、并且由于 高达 ，输出建议用 printf 或手写快写。完整代码：

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

4
typedef long long ll;
5

6
int compare(ll a, ll b, ll c, ll d) {
7
  __int128 x = (__int128)a * d - (__int128)c * b;
8
  return x > 0 ? 1 : (x < 0 ? -1 : 0);
9
}
10

11
int main() {
12
  int T;
13
  scanf("%d", &T);
14
  while (T--) {
15
    ll A, B, C, D;
16
    scanf("%lld%lld%lld%lld", &A, &B, &C, &D);
17
    ll lu = 0, lv = 1, ru = 1, rv = 0, cu = 1, cv = 1;
18
    while (true) {
19
      if (compare(cu, cv, A, B) > 0 && compare(cu, cv, C, D) < 0) break;
20
      if (compare(cu, cv, A, B) <= 0) {
21
        ll t = (ll)(((__int128)A * cv - (__int128)cu * B) / ((__int128)ru * B - (__int128)A * rv));
22
        if (t < 1) t = 1;
23
        lu = cu + (t - 1) * ru, lv = cv + (t - 1) * rv;
24
      } else {
25
        ll t = (ll)(((__int128)cu * D - (__int128)C * cv) / ((__int128)C * lv - (__int128)lu * D));
26
        if (t < 1) t = 1;
27
        ru = cu + (t - 1) * lu, rv = cv + (t - 1) * lv;
28
      }
29
      cu = lu + ru, cv = lv + rv;
30
    }
31
    printf("%lld\n", cv);
32
  }
33
  return 0;
34
}

这份代码在样例上的输出为 3 5 1 226 4，与题目给出的答案一致。由于每次换向都会让分子或分母至少翻倍，循环次数是 级别的， 组数据可以轻松跑完。

至于我是怎么确认这份代码不会因为 t = 0 死循环的……对拍机告诉我，别问。