結果

問題 No.2183 LCA on Rational Tree
ユーザー ああいいああいい
提出日時 2023-01-14 18:05:05
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,456 bytes
コンパイル時間 390 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 78,536 KB
最終ジャッジ日時 2024-06-07 18:59:25
合計ジャッジ時間 8,640 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
57,216 KB
testcase_01 AC 1,846 ms
77,056 KB
testcase_02 TLE -
testcase_03 AC 1,107 ms
77,056 KB
testcase_04 AC 372 ms
76,288 KB
testcase_05 AC 1,849 ms
78,536 KB
権限があれば一括ダウンロードができます

ソースコード

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,l):
    d = q - p
    if d == 1:
        return 10 ** 10
    tmp = 10 ** 10
    for k in l:
        if k > d:break
        if d % k == 0:
            u = k - p % k
            if u < tmp:tmp = u
    return tmp

def div(d):
    l = set()
    i = 1
    while i * i <= d:
        if d % i == 0:
            if i > 1:
                l.add(i)
            l.add(d // i)
        i += 1
    return sorted(l)
    
for _ in range(Q):
    p,q,r,s = map(int,rr.readline().split())

    l = div(q - p)
    ll = div(s - r)
    
    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,l)
            g = gcd(p + n,q + n)
            p = (p + n) // g
            q = (q + n) // g
        elif dd > d:
            n = calc(r,s,ll)
            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
                l,ll = ll,l
            n = calc(p,q,l)
            if q + n > s:
                print(r,s)
                break
            else:
                g = gcd(p + n,q + n)
                p = (p + n) // g
                q = (q + n) // g
0