ACdream 1187：Calkin-Wilf 樹的雙向查找（nth 元素與排名）

無限二元樹結構與性質

根節點 1/1。節點 p/q 的左子節點 p/(p+q)，右子節點 (p+q)/q。
層序遍歷得到序列：1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, ...
關鍵性質：每個正有理數恰好出現一次（Calkin-Wilf 樹）。

問題雙向查詢

• Type 1：給 n (1 ≤ n ≤ 2^64-1)，求第 n 個分數 p/q
• Type 2：給 p/q，求其在序列中的位置 n

核心規律：二進制路徑編碼

觀察樹結構：
- 根 = 1 (二進制 1)
- 左子 = 父 * 2，右子 = 父 * 2 + 1
即：節點在層序中的位置 n，其二進制表示編碼了從根到該節點的路徑（去掉最高位 1 後，0=左，1=右）。

Type 1：n → p/q（自上而下）

void solve1(unsigned long long n) {
    unsigned long long p = 1, q = 1;
    // 找最高位
    int h = 63;
    while ((n >> h) == 0) h--;
    // 從次高位到最低位
    for (int i = h - 1; i >= 0; i--) {
        if ((n >> i) & 1) { // 1 = 右
            p = p + q;
        } else { // 0 = 左
            q = p + q;
        }
    }
    printf("%llu %llu\n", p, q);
}

Type 2：p/q → n（自下而上）

unsigned long long solve2(unsigned long long p, unsigned long long q) {
    unsigned long long n = 1; // 根位置
    unsigned long long bit = 1; // 當前位權
    while (!(p == 1 && q == 1)) {
        if (p < q) { // 左子：p/q = p/(p+q) → 父 = p/(q-p)
            q = q - p;
            // 左子對應位 0，n 不變，但位權左移
        } else { // 右子：p/q = (p+q)/q → 父 = (p-q)/q
            p = p - q;
            n |= bit; // 右子對應位 1
        }
        bit <<= 1;
    }
    return n;
}

完整代碼與大數處理

#include 
#include 
using namespace std;

typedef unsigned long long ull;

ull nth_to_frac(ull n, ull &p, ull &q) {
    p = q = 1;
    int h = 63;
    while (h >= 0 && ((n >> h) == 0)) h--;
    for (int i = h - 1; i >= 0; i--) {
        if ((n >> i) & 1) p += q;
        else q += p;
    }
}

ull frac_to_nth(ull p, ull q) {
    ull n = 1, bit = 1;
    while (p != 1 || q != 1) {
        if (p < q) q -= p;
        else { p -= q; n |= bit; }
        bit <<= 1;
    }
    return n;
}

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        int type; scanf("%d", &type);
        if (type == 1) {
            ull n, p, q; scanf("%llu", &n);
            nth_to_frac(n, p, q);
            printf("Case #%d: %llu %llu\n", cas, p, q);
        } else {
            ull p, q; scanf("%llu%llu", &p, &q);
            ull n = frac_to_nth(p, q);
            printf("Case #%d: %llu\n", cas, n);
        }
    }
    return 0;
}

關鍵點總結

• 無符號 64 位：n, p, q 可達 2^64-1，必須用 unsigned long long
• 遞歸關系：左子 (p, p+q)，右子 (p+q, q) → 逆向：p
• 二進制路徑：層序編號 n 的二進制編碼路徑，最高位 1 為根，後續 0=左 1=右
• 複雜度：O(log n) = O(64)，極快

這道題巧妙利用了 Calkin-Wilf 樹與二進制表示的深層聯系，將分數運算轉化為位運算，是數論與樹結構結合的經典例題。