結果
問題 |
No.2183 LCA on Rational Tree
|
ユーザー |
![]() |
提出日時 | 2024-06-02 03:57:27 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,185 bytes |
コンパイル時間 | 366 ms |
コンパイル使用メモリ | 82,448 KB |
実行使用メモリ | 79,000 KB |
最終ジャッジ日時 | 2024-12-22 20:58:23 |
合計ジャッジ時間 | 9,613 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 4 WA * 1 TLE * 1 |
ソースコード
import math from collections import defaultdict 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**9 def tree(p,q): D=Divisors(q-p) def f(p,q): if q-p==1: return [(1,p,M)] lst=[] for d in D[1:]: if (q-p)%d==0: lst.append((-p)%d) mi=min(lst) pp=p+mi qq=q+mi g=math.gcd(pp,qq) return [(q-p,pp,pp)]+f(pp//g,qq//g) return f(p,q) tree0=tree(a,b) tree1=tree(c,d) dct=defaultdict(list) for d,a,b in tree0+tree1: dct[d].append((a,b)) lst=[] for d in dct: if len(dct[d])==2: (a0,b0),(a1,b1)=dct[d] a=max(a0,a1) b=min(b0,b1) if a<=b: lst.append((d,a)) d,a=min(lst) print(a,a+d)