結果

問題 No.2183 LCA on Rational Tree
ユーザー qwewe
提出日時 2025-05-14 13:19:23
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,125 bytes
コンパイル時間 437 ms
コンパイル使用メモリ 82,568 KB
実行使用メモリ 439,348 KB
最終ジャッジ日時 2025-05-14 13:20:39
合計ジャッジ時間 6,896 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
import sys

# Function to compute the greatest common divisor (GCD) efficiently.
# Using math.gcd is generally fast as it's likely implemented in C.
def gcd(a, b):
    """Computes the greatest common divisor of a and b."""
    return math.gcd(a, b)

def solve():
    """Solves a single query for LCA."""
    
    # Read the input fractions p(u)/q(u) and p(v)/q(v)
    P = list(map(int, sys.stdin.readline().split()))
    pu1, qu1, pv1, qv1 = P[0], P[1], P[2], P[3]

    # Dictionary to store the nodes encountered along the path starting from u1.
    # Key: tuple (p, q) representing the rational number p/q.
    # Value: The number of steps taken from u1 to reach this node. Useful for debugging or potential optimizations, but not strictly needed for finding LCA here.
    u_path = {}
    
    # Start tracing the path from u1 = pu1/qu1
    curr_p = pu1
    curr_q = qu1
    
    # Set a maximum number of steps to prevent excessively long computations or potential infinite loops.
    # This value is chosen based on typical competitive programming constraints and problem analysis.
    # If path length exceeds this, the solution might Time Limit Exceed or fail on edge cases.
    # Based on problem constraints and typical behavior of such structures, 2*10^6 seems reasonable.
    MAX_STEPS = 2 * 10**6 
    
    # Generate the path starting from u1
    count = 0
    while count < MAX_STEPS:
        # Store the current node (p, q) and its step count (distance from u1)
        u_path[(curr_p, curr_q)] = count
        
        # Calculate the next node p'/q' by applying the operation: (p+1)/(q+1) simplified.
        next_p_num = curr_p + 1
        next_q_num = curr_q + 1
        
        # Find the greatest common divisor of numerator and denominator to simplify the fraction.
        common_divisor = gcd(next_p_num, next_q_num)
        
        # Compute the simplified numerator and denominator for the next node.
        # Integer division // is used.
        next_p = next_p_num // common_divisor
        next_q = next_q_num // common_divisor
        
        # Optional check: if the state (p, q) doesn't change, break to avoid potential infinite loop.
        # This condition shouldn't be met for valid inputs in the vertex set V defined as 1 <= p < q.
        if next_p == curr_p and next_q == curr_q:
             break 

        # Move to the next node
        curr_p = next_p
        curr_q = next_q
        
        count += 1

    # Now, trace the path starting from v1 = pv1/qv1
    curr_p = pv1
    curr_q = qv1
    
    count = 0
    while count < MAX_STEPS:
        # Check if the current node (p, q) from v1's path exists in the path generated from u1.
        # The `in` check on dictionary keys is O(1) on average.
        if (curr_p, curr_q) in u_path:
            # If found, this is the first common node encountered, which is the Lowest Common Ancestor (LCA).
            # Print its numerator and denominator.
            print(f"{curr_p} {curr_q}")
            # Return after finding the LCA for this query.
            return 

        # Calculate the next node in the path from v1
        next_p_num = curr_p + 1
        next_q_num = curr_q + 1
        
        common_divisor = gcd(next_p_num, next_q_num)
        
        next_p = next_p_num // common_divisor
        next_q = next_q_num // common_divisor
        
        # Optional check: state doesn't change
        if next_p == curr_p and next_q == curr_q:
             break

        # Move to the next node
        curr_p = next_p
        curr_q = next_q
        
        count += 1

    # If this point is reached, it means the LCA was not found within MAX_STEPS.
    # This could happen if MAX_STEPS is too small for some test cases, or if there's an issue
    # with the understanding of the problem structure (e.g., paths diverge indefinitely or cycle differently).
    # For the contest setting, it's usually assumed that a solution exists within reasonable bounds.


# Read the number of queries from standard input
Q = int(sys.stdin.readline())
# Process each query one by one
for _ in range(Q):
    solve()
0