题解：P16470 [GKS 2013 #A] Rational Number Tree

Rainmount · 2026-05-17 21:41:37 · 题解

P16470 [GKS 2013 #A] Rational Number Tree

题目传送门

蒟蒻的第二篇题解，还请管理员大大手下留情。

观前提示：本文经过 Qwen 3.6 润色，保证本人功劳不小于 AI。

思路

这棵树叫 Calkin-Wilf 树神秘翻译：靠金威尔福树，有个很不妙的性质：每个正有理数恰好出现一次。太糟糕了这使得我们很快就可以写出来。

先观察层序遍历的编号规律：

• 根节点编号为 1。
• 节点 i 的左子编号 2 \times i，右子编号 2 \times i + 1。

把编号 n 写成二进制，去掉最高位的 1，剩下的每一位就表示从根出发的路径：0 表示往左走，1 表示往右走。

比如 n = 5，二进制是 101，去掉最高位剩 01：

• 根 \frac{1}{1} → 左（0）→ \frac{1}{2} → 右（1）→ \frac{3}{2} 这就很对滴。

问题 1（已知 n 求分数）：

• 从 \frac{1}{1} 出发，按 n 的二进制位（从高到低）模拟走树：左子 \frac{p}{p+q}，右子 \frac{p+q}{q}。

问题 2（已知 \frac{p}{q} 求位置）：

• 反过来从 \frac{p}{q} 往上爬回根：
  • 若 p < q，说明当前是左子，父节点为 \frac{p}{q-p}，记录 0。
  • 若 p > q，说明当前是右子，父节点为 \frac{p-q}{q}，记录 1。
• 这样得到的路径是「叶子→根」，反转后才是「根→叶子」。
• 把反转后的路径拼到二进制 1 后面，转成十进制就是答案。

数据范围到 2^{64}-1，记得用 unsigned long long，最多爬 64 层，完全不会 TLE。

AC CODE

不要照抄哦，小心变棕清空 AC 记录。

#include<bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    for (int cas = 1; cas <= T; cas++) {
        int op; cin >> op;
        if (op == 1) {
            ull n; cin >> n;
            ull p = 1, q = 1;
            // 找最高位
            int hb = 63;
            while (hb >= 0 && !(n >> hb & 1)) hb--;
            // 按路径走
            for (int i = hb - 1; i >= 0; i--) {
                if (n >> i & 1) p = p + q;  // 右
                else q = p + q;              // 左
            }
            cout << "Case #" << cas << ": " << p << " " << q << "\n";
        } else {
            ull p, q; cin >> p >> q;
            vector<int> bit;
            while (p != 1 || q != 1) {
                if (p < q) {
                    bit.push_back(0);  // 左子
                    q -= p;
                } else {
                    bit.push_back(1);  // 右子
                    p -= q;
                }
            }
            // 反转路径 + 拼二进制
            ull n = 1;
            for (int i = (int)bit.size() - 1; i >= 0; i--)
                n = (n << 1) | bit[i];
            cout << "Case #" << cas << ": " << n << "\n";
        }
    }
    return 0;
// 有理数树，拿捏！
// By Rainmount
}