結果
| 問題 | No.3307 Almost Equal | 
| コンテスト | |
| ユーザー |  hir355 | 
| 提出日時 | 2025-10-05 15:49:53 | 
| 言語 | PyPy3 (7.3.15) | 
| 結果 | 
                                AC
                                 
                             | 
| 実行時間 | 36 ms / 2,000 ms | 
| コード長 | 1,163 bytes | 
| コンパイル時間 | 514 ms | 
| コンパイル使用メモリ | 82,324 KB | 
| 実行使用メモリ | 54,284 KB | 
| 最終ジャッジ日時 | 2025-10-05 15:50:13 | 
| 合計ジャッジ時間 | 3,363 ms | 
| ジャッジサーバーID (参考情報) | judge3 / judge5 | 
(要ログイン)
| ファイルパターン | 結果 | 
|---|---|
| sample | AC * 3 | 
| other | AC * 46 | 
ソースコード
def floor_sum(n, m, a, b):
   a1, a2 = a // m, a % m
   s = n * (n - 1) // 2 * a1
   b1, b2 = b // m, b % m
   if a2 == 0:
       return s + b1 * n
   k = (a2 * (n - 1) + b2) // m
   return s + n * (k + b1) - floor_sum(k, a2, m, m + a2 - b2 - 1)
a, b, c, d = map(int, input().split())
if a * d == b * c:
    print(-1)
    exit(0)
if a * d < b * c:
    a, b, c, d = c, d, a, b
ans = 0
m = b * d // (a * d - b * c)
ng, ok = -1, 10 ** 20 + 1
while ok - ng > 1:
    md = (ok + ng) // 2
    if ((2 * md + 1) * b - 1) // (2 * a) + 1 >= m:
        ok = md
    else:
        ng = md
n2 = ok
ng, ok = -1, 10 ** 20 + 1
while ok - ng > 1:
    md = (ok + ng) // 2
    if ((2 * md + 1) * d - 1) // (2 * c) + 1 >= m:
        ok = md
    else:
        ng = md
n1 = ok
l = floor_sum(n2, 2 * a, 2 * b, b - 1) + n2
r = floor_sum(n1, 2 * c, 2 * d, d - 1) + n1 + m * (n2 - n1)
print(m - (r - l) - 1)
# cr, cl = 0, 0
# n  = 0
# while 1:
#     r = ((2 * n + 1) * d - 1) // (2 * c) + 1
#     cr += min(r, m)
#     l = ((2 * n + 1) * b - 1) // (2 * a) + 1
#     cl += min(l, m)
#     t = min(r, m) - min(l, m)
#     if l >= m:
#         break
#     ans += t
#     n += 1
# print(cl, cr)
            
            
            
        