結果

問題 No.2183 LCA on Rational Tree
ユーザー lam6er
提出日時 2025-04-16 16:33:28
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 774 bytes
コンパイル時間 600 ms
コンパイル使用メモリ 82,472 KB
実行使用メモリ 68,504 KB
最終ジャッジ日時 2025-04-16 16:36:12
合計ジャッジ時間 4,187 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import math

def compute_base(p, q):
    d = q - p
    while d > 1:
        g = math.gcd(p + 1, q + 1)
        new_p = (p + 1) // g
        new_q = (q + 1) // g
        p, q = new_p, new_q
        d = q - p
    return (p, q)

Q = int(input())
for _ in range(Q):
    p1, q1, p2, q2 = map(int, input().split())
    
    # Compute base nodes
    base1_p, base1_q = compute_base(p1, q1)
    base2_p, base2_q = compute_base(p2, q2)
    
    # Compare the base nodes
    if (base1_p, base1_q) == (base2_p, base2_q):
        l_p, l_q = base1_p, base1_q
    else:
        # In the difference 1 phase, the LCA is the one with larger p
        if base1_p > base2_p:
            l_p, l_q = base1_p, base1_q
        else:
            l_p, l_q = base2_p, base2_q
    
    print(l_p, l_q)
0