P16470 [GKS 2013 #A] Rational Number Tree
题目描述
考虑一棵无限完全二叉树，其中根节点为 $1/1$，节点 $p/q$ 的左子节点和右子节点分别为 $p/(p+q)$ 和 $(p+q)/q$。这棵树如下图所示：
:::align{center}
:::
已知每个正有理数在这棵树中恰好出现一次。对这棵树进行层序遍历，得到如下序列：
$1/1$, $1/2$, $2/1$, $1/3$, $3/2$, $2/3$, $3/1$, $\dots$
请解决以下两个问题：
1. 找到序列中的第 $n$ 个元素，其中 $n$ 从 $1$ 开始。例如，对于输入 $2$，正确的输出是 $1/2$。
2. 给定 $p/q$，找到它在序列中的位置。例如，输入 $1/2$ 会得到输出 $2$。
输入格式
第一行输入包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例占一行，包含一个问题编号（$1$ 或 $2$）以及一个或两个额外的整数：
1. 如果问题编号为 $1$，则只给出一个整数 $n$，你需要找到序列中的第 $n$ 个元素。
2. 如果问题编号为 $2$，则给出两个整数 $p$ 和 $q$，你需要找到 $p/q$ 在序列中的位置。
输出格式
对于每个测试用例：
1. 如果问题编号为 $1$，则输出一行形如 "Case #x: p q" 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$p, q$ 分别是所求序列元素的分子和分母。
2. 如果问题编号为 $2$，则输出一行形如 "Case #x: n" 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$n$ 是给定数字的位置。
说明/提示
### 限制
$1 \le T \le 100$；$p$ 与 $q$ 互质。
**测试集 1 - 可见**
$1 \le n, p, q \le 2^{16}-1$；$p/q$ 是层编号不超过 $16$ 的树中的元素。
**测试集 2 - 隐藏**
$1 \le n, p, q \le 2^{64}-1$；$p/q$ 是层编号不超过 $64$ 的树中的元素。
翻译由 DeepSeek V4 Pro 完成