結果

問題 No.2183 LCA on Rational Tree
ユーザー ああいい
提出日時 2023-01-14 17:54:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,306 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 192 ms
コンパイル使用メモリ 81,752 KB
実行使用メモリ 153,864 KB
最終ジャッジ日時 2024-12-26 03:10:56
合計ジャッジ時間 11,711 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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