結果
| 問題 | No.3307 Almost Equal | 
| コンテスト | |
| ユーザー |  dp_ijk | 
| 提出日時 | 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))
            
            
            
        