結果
問題 | 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=0bp=0pre=0ans=0while True:if ap==len(A)-1 and bp==len(B)-1:breaknex=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)*aybx+=(B[bp]-nex)*bydiv=nex-preif ax>=bx and ay>=by:ans+=divelif ax<bx and ay<by:ans+=0elif ax>=bx and ay<by:ans+=min(div,(ax-bx)//(by-ay)+1)pre=nexif A[ap]==nex:ap+=1if B[bp]==nex:bp+=1print(ans)