結果

問題 No.2183 LCA on Rational Tree
ユーザー ああいいああいい
提出日時 2023-01-14 17:54:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,306 bytes
コンパイル時間 163 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 81,536 KB
最終ジャッジ日時 2024-06-07 18:51:33
合計ジャッジ時間 6,556 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
62,336 KB
testcase_01 TLE -
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
rr = sys.stdin

Q = int(rr.readline())


def gcd(a,b):
    if b == 0:return a
    while True:
        r = a % b
        a = b
        b = r
        if r == 0:return a

def calc(p,q):
    d = q - p
    if d == 1:
        return 10 ** 10
    tmp = 10 ** 10
    i = 1
    while i * i <= d:
        if d % i == 0:
            if i > 1:
                u = i - p % i
                if u < tmp:tmp = u
            j = d // i
            u = j - p % j
            if u < tmp:tmp = u
        i += 1
    return tmp
    
    
for _ in range(Q):
    p,q,r,s = map(int,rr.readline().split())

    while True:
        if p == r and q == s:
            print(p,q)
            break
        d = q - p
        dd = s - r
        if d > dd:
            n = calc(p,q)
            g = gcd(p + n,q + n)
            p = (p + n) // g
            q = (q + n) // g
        elif dd > d:
            n = calc(r,s)
            g = gcd(r + n,s + n)
            r = (r + n) // g
            s = (s + n) // g
        else:
            if q > s:
                s,q = q,s
                p,r = r,p
            n = calc(p,q)
            if q + n > s:
                print(r,s)
                break
            else:
                g = gcd(p + n,q + n)
                p = (p + n) // g
                q = (q + n) // g
0