結果

問題 No.2183 LCA on Rational Tree
ユーザー ああいいああいい
提出日時 2023-01-14 18:26:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 432 ms / 2,000 ms
コード長 1,670 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 81,840 KB
実行使用メモリ 78,236 KB
最終ジャッジ日時 2024-06-07 19:17:09
合計ジャッジ時間 2,401 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 49 ms
61,724 KB
testcase_01 AC 357 ms
78,048 KB
testcase_02 AC 432 ms
77,476 KB
testcase_03 AC 404 ms
78,236 KB
testcase_04 AC 187 ms
77,720 KB
testcase_05 AC 234 ms
77,876 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] = 1
#print(prime[:20])
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