SternBrocot_LCA.cpp

#include <iostream>
#include <utility>

using namespace std;

/*
 * 比較兩個分數 a/b 與 p/q 的大小
 * 為了避免浮點誤差，使用交叉相乘：
 *   a/b < p/q  <==>  a*q < b*p  (因為 b, q 均為正數)
 *
 * 回傳：
 *  -1  表示 a/b < p/q
 *   0  表示 a/b = p/q
 *  +1  表示 a/b > p/q
 */
int comp (long long a, long long b, long long p, long long q) {
    long long lhs = a * q;
    long long rhs = b * p;

    if (lhs < rhs) return -1;
    if (lhs > rhs) return 1;

    return 0;
}

/*
 * 在 Stern-Brocot Tree 上尋找 a1/b1 與 a2/b2 的最近共同祖先 (LCA)
 *
 * Stern-Brocot Tree 的建構原理：
 *   - 從虛擬邊界 lo = 0/1（左）和 hi = 1/0（右）出發
 *   - 每次取中位數 mid = (lo.分子 + hi.分子) / (lo.分母 + hi.分母)
 *   - mid 即為目前層的節點；比 mid 小往左（hi = mid），比 mid 大往右（lo = mid）
 *
 * LCA 的判斷邏輯：
 *   - 同時對兩個分數做搜尋，每步讓兩者一起移動
 *   - 若兩個分數都在 mid 的左邊 → 都往左走
 *   - 若兩個分數都在 mid 的右邊 → 都往右走
 *   - 否則（一左一右，或其中一個恰好等於 mid）→ 當前 mid 就是 LCA
 *
 * 回傳：LCA 的分子與分母，以 pair<分子, 分母> 表示
 */
pair<long long, long long> lca (long long a1, long long b1,
                                long long a2, long long b2) {

    long long lo_n = 0, lo_d = 1;
    long long hi_n = 1, hi_d = 0;

    while (true) {
        // 計算目前的中位數（當前節點）
        // Stern-Brocot 中位數公式：分子相加 / 分母相加
        long long mid_n = lo_n + hi_n;
        long long mid_d = lo_d + hi_d;

        // 判斷兩個目標分數各自與 mid 的大小關係
        int c1 = comp(a1, b1, mid_n, mid_d);
        int c2 = comp(a2, b2, mid_n, mid_d);

        if (c1 < 0 && c2 < 0) {
            // 兩個分數都小於 mid，LCA 必定在左子樹
            // → 縮小右邊界，往左走
            hi_n = mid_n;
            hi_d = mid_d;
        }
        else if (c1 >0 && c2 > 0) {
            // 兩個分數都大於 mid，LCA 必定在右子樹
            // → 縮小左邊界，往右走
            lo_n = mid_n;
            lo_d = mid_d;
        }
        else {
            // 以下三種情況，mid 都是 LCA：
            //   (1) a1/b1 < mid 且 a2/b2 > mid → 分叉，mid 是最近的共同祖先
            //   (2) a1/b1 > mid 且 a2/b2 < mid → 分叉，mid 是最近的共同祖先
            //   (3) a1/b1 = mid 或 a2/b2 = mid → 其中一個就是 mid 本身，
            //       mid 自然是另一個的祖先，也是兩者的 LCA
            return {mid_n, mid_d};
        }
    }
}

int main() {

    long long a1, b1, a2, b2;

    while (cin >> a1 >> b1 >> a2 >> b2) {
        if (a1 ==0 && b1 == 0 && a2 == 0 && b2 == 0) break;

        // 求 LCA 並輸出（題目要求格式為 "分子 分母"）
        pair<long long, long long> result = lca(a1, b1, a2, b2);
        cout << result.first << " " << result.second << endl;
    }
    return 0;
}