結果
問題 |
No.2183 LCA on Rational Tree
|
ユーザー |
![]() |
提出日時 | 2024-06-02 04:49:55 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,287 bytes |
コンパイル時間 | 158 ms |
コンパイル使用メモリ | 82,224 KB |
実行使用メモリ | 80,696 KB |
最終ジャッジ日時 | 2024-12-22 22:17:17 |
合計ジャッジ時間 | 5,128 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 5 TLE * 1 |
ソースコード
import math from functools import lru_cache @lru_cache(maxsize=None) def Divisors(N): divisors=[] for i in range(1,N+1): if i**2>=N: break elif N%i==0: divisors.append(i) if i**2==N: divisors+=[i]+[N//i for i in divisors[::-1]] else: divisors+=[N//i for i in divisors[::-1]] return divisors Q=int(input()) for q in range(Q): a,b,c,d=map(int,input().split()) M=10**18 def tree(p,q): retu=[] D=Divisors(q-p) while q-p>=2: mi=min((-p)%d for d in D[1:] if (q-p)%d==0) pp=p+mi qq=q+mi g=math.gcd(pp,qq) retu.append((q-p,p,pp)) p,q=pp//g,qq//g retu.append((1,p,M)) return retu tree0=tree(a,b) tree1=tree(c,d) assert len(tree0)<=30 assert len(tree1)<=30 D,A=M,M tree0.sort() tree1.sort() while tree0 and tree1: if tree0[-1][0]<tree1[-1][0]: tree1.pop() elif tree0[-1][0]>tree1[-1][0]: tree0.pop() else: d0,a0,b0=tree0.pop() d1,a1,b1=tree1.pop() a=max(a0,a1) b=min(b0,b1) d=d0 if a<=b: D,A=min((D,A),(d,a)) print(A,A+D)