結果

問題 No.2183 LCA on Rational Tree
ユーザー gew1fw
提出日時 2025-06-12 18:46:27
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,291 bytes
コンパイル時間 184 ms
コンパイル使用メモリ 81,992 KB
実行使用メモリ 364,756 KB
最終ジャッジ日時 2025-06-12 18:46:35
合計ジャッジ時間 4,543 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def simulate_path(p, q):
    path = []
    current_p, current_q = p, q
    path.append((current_p, current_q))
    while True:
        d = current_q - current_p
        if d == 1:
            break
        g = gcd(current_p + 1, d)
        new_p = (current_p + 1) // g
        new_q = (current_q + 1) // g
        current_p, current_q = new_p, new_q
        path.append((current_p, current_q))
    return path

def main():
    input = sys.stdin.read().split()
    idx = 0
    Q = int(input[idx])
    idx +=1
    for _ in range(Q):
        p1 = int(input[idx])
        q1 = int(input[idx+1])
        p2 = int(input[idx+2])
        q2 = int(input[idx+3])
        idx +=4
        
        path_u = simulate_path(p1, q1)
        path_v = simulate_path(p2, q2)
        
        set_v = set(path_v)
        lca = None
        for node in path_u:
            if node in set_v:
                lca = node
                break
        if lca is None:
            entry_u = path_u[-1]
            entry_v = path_v[-1]
            if entry_v[1] > entry_u[1]:
                lca = entry_v
            else:
                lca = entry_u
        print(f"{lca[0]} {lca[1]}")

if __name__ == "__main__":
    main()
0