結果
問題 |
No.3307 Almost Equal
|
ユーザー |
![]() |
提出日時 | 2025-10-05 15:24:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 144 ms / 2,000 ms |
コード長 | 1,213 bytes |
コンパイル時間 | 324 ms |
コンパイル使用メモリ | 82,592 KB |
実行使用メモリ | 89,272 KB |
最終ジャッジ日時 | 2025-10-05 15:25:13 |
合計ジャッジ時間 | 8,276 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
def floor_sum(N: int, M: int, A: int, B: int) -> int: if N <= 0: return 0 assert M != 0 if M < 0: return floor_sum(N, -M, -A, -B) assert 1 <= M res = 0 while True: if not 0 <= A < M: qA, A = divmod(A, M) res += N*(N-1) // 2 * qA if not 0 <= B < M: qB, B = divmod(B, M) res += N*qB last = A*(N-1) + B if M <= last: q, r = divmod(last, M) res += q N, M, A, B = q, A, M, r continue return res def floor_sum_range(range: tuple[int, int], M: int, coef: int, bias: int): L, R = range if not (L < R): return 0 return floor_sum(R-L, M, coef, coef*L + bias) from fractions import Fraction def solve(A, B, C, D): X = Fraction(A, B) Y = Fraction(C, D) if X == Y: return -1 if not (X < Y): X, Y = Y, X (A, B), (C, D) = (C, D), (A, B) assert X < Y Z = (Y-X) U = (1/Z).__ceil__() - 1 cnt = U sm = floor_sum_range((1, U+1), M=2*D, coef=2*C, bias=D) sm2 = floor_sum_range((1, U+1), M=2*B, coef=2*A, bias=B) assert sm2 <= sm cnt -= (sm - sm2) return cnt A, B, C, D = map(int, input().split()) print(solve(A, B, C, D))