結果
問題 |
No.2882 Comeback
|
ユーザー |
|
提出日時 | 2024-09-08 12:58:02 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 224 ms / 2,000 ms |
コード長 | 1,000 bytes |
コンパイル時間 | 366 ms |
コンパイル使用メモリ | 82,032 KB |
実行使用メモリ | 123,104 KB |
最終ジャッジ日時 | 2024-09-08 12:58:08 |
合計ジャッジ時間 | 5,756 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
t=int(input()) for _ in range(t): a,b=map(int,input().split()) ra=int(a**(1/2)) rb=int(b**(1/2)) AA=[] for i in range(1,ra+1): AA.append(a//i) A=list(range(1,AA[-1])) A+=list(reversed(AA))+[b]+[-1] BB=[] for i in range(1,rb+1): BB.append(b//i) B=list(range(1,BB[-1])) B+=list(reversed(BB))+[-1] #print(*A) #print(*B) ap=0 bp=0 pre=0 ans=0 while True: if ap==len(A)-1 and bp==len(B)-1: break nex=min(A[ap],B[bp]) ax=a%A[ap] bx=b%B[bp] ay=a//A[ap] by=b//B[bp] ax+=(A[ap]-nex)*ay bx+=(B[bp]-nex)*by div=nex-pre if ax>=bx and ay>=by: ans+=div elif ax<bx and ay<by: ans+=0 elif ax>=bx and ay<by: ans+=min(div,(ax-bx)//(by-ay)+1) pre=nex if A[ap]==nex: ap+=1 if B[bp]==nex: bp+=1 print(ans)