結果
問題 |
No.2882 Comeback
|
ユーザー |
|
提出日時 | 2024-09-07 13:35:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 271 ms / 2,000 ms |
コード長 | 621 bytes |
コンパイル時間 | 580 ms |
コンパイル使用メモリ | 82,356 KB |
実行使用メモリ | 149,068 KB |
最終ジャッジ日時 | 2024-09-07 13:35:27 |
合計ジャッジ時間 | 6,488 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
from math import isqrt for _ in range(int(input())): A, B = map(int, input().split()) change = set() for d in range(1, isqrt(A) + 1): change.add(d) change.add(A // d) for d in range(1, isqrt(B) + 1): change.add(d) change.add(B // d) change = list(change) change.sort(reverse = True) N = len(change) change.append(0) ans = 0 for i in range(N): fa, fb = A % change[i], B % change[i] da, db = A // change[i], B // change[i] l = change[i] - change[i + 1] if da == db: if fa >= fb: ans += l continue if fa < fb: continue x = (fa - fb) // (db - da) ans += min(l, x + 1) print(ans)