結果

問題 No.2183 LCA on Rational Tree
ユーザー ああいいああいい
提出日時 2023-01-14 18:25:39
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,652 bytes
コンパイル時間 203 ms
コンパイル使用メモリ 82,032 KB
実行使用メモリ 78,580 KB
最終ジャッジ日時 2024-06-07 19:16:17
合計ジャッジ時間 9,346 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 53 ms
65,260 KB
testcase_01 AC 1,793 ms
78,580 KB
testcase_02 TLE -
testcase_03 TLE -
testcase_04 AC 714 ms
78,396 KB
testcase_05 AC 685 ms
78,124 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

prime = []
C = 4 * 10 ** 4
dat = [0] *C
for i in range(2,C):
    if dat[i] == 0:
        prime.append(i)
        for j in range(i,C,i):
            dat[j] = 0

def div(d):
    l = []

    for p in prime:
        if p > d:break
        if d % p == 0:
            l.append(p)
            d //= p
            while d % p == 0:
                d //= p
    if d > 1:l.append(d)
    return 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