結果

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

ソースコード

diff # 

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