結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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))
0