結果

問題 No.3307 Almost Equal
コンテスト
ユーザー detteiuu
提出日時 2026-02-13 21:54:40
言語 PyPy3
(7.3.17)
結果
WA  
実行時間 -
コード長 2,656 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 436 ms
コンパイル使用メモリ 82,368 KB
実行使用メモリ 55,264 KB
最終ジャッジ日時 2026-02-13 21:54:45
合計ジャッジ時間 4,651 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 44 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from math import gcd

def floor_sum(n, m, a, b):
    ans = 0
    while True:
        if a >= m or a < 0:
            ans += n * (n - 1) * (a // m) // 2
            a %= m
        if b >= m or b < 0:
            ans += n * (b // m)
            b %= m
        y_max = a * n + b
        if y_max < m: break
        n, b, m, a = y_max // m, y_max % m, a, m
    return ans

from math import gcd

class Fraction:
    def __init__(self, top, bottom):
        GCD = gcd(top, bottom)
        if bottom < 0:
            top = -top
            bottom = -bottom
        self.top = top//GCD
        self.bottom = bottom//GCD

def to_fraction(n):
    if type(n) == int:
        return Fraction(n, 1)
    else:
        return n

def compare(L, R):
    L, R = to_fraction(L), to_fraction(R)
    a = L.top*R.bottom
    b = L.bottom*R.top
    if a < b:
        return -1
    elif a == b:
        return 0
    else:
        return 1
    
def max_f(L, R):
    return L if compare(L, R) == 1 else R

def min_f(L, R):
    return L if compare(L, R) == -1 else R

def ADD(L, R):
    L, R = to_fraction(L), to_fraction(R)
    l, r = L.bottom, R.bottom
    lt = L.top*r
    rt = R.top*l
    top = lt+rt
    bottom = l*r
    GCD = gcd(top, bottom)
    top //= GCD
    bottom //= GCD
    if bottom < 0:
        top = -top
        bottom = -bottom
    return Fraction(top, bottom)

def SUB(L, R):
    L, R = to_fraction(L), to_fraction(R)
    l, r = L.bottom, R.bottom
    lt = L.top*r
    rt = R.top*l
    top = lt-rt
    bottom = l*r
    GCD = gcd(top, bottom)
    top //= GCD
    bottom //= GCD
    if bottom < 0:
        top = -top
        bottom = -bottom
    return Fraction(top, bottom)

def MUL(L, R):
    L, R = to_fraction(L), to_fraction(R)
    top = L.top*R.top
    bottom = L.bottom*R.bottom
    GCD = gcd(top, bottom)
    top //= GCD
    bottom //= GCD
    if bottom < 0:
        top = -top
        bottom = -bottom
    return Fraction(top, bottom)

def DIV(L, R):
    L, R = to_fraction(L), to_fraction(R)
    top = L.top*R.bottom
    bottom = L.bottom*R.top
    GCD = gcd(top, bottom)
    top //= GCD
    bottom //= GCD
    if bottom < 0:
        top = -top
        bottom = -bottom
    return Fraction(top, bottom)

A, B, C, D = map(int, input().split())

if compare(Fraction(A, B), Fraction(C, D)) == 0:
    exit(print(-1))

if compare(Fraction(A, B), Fraction(C, D)) == 1:
    A, B, C, D = C, D, A, B

left = 0
right = 10**12
while left+1 < right:
    mid = (left+right)//2
    if compare(ADD(Fraction(A*mid, B), 1), Fraction(C*mid, D)) == 1:
        left = mid
    else:
        right = mid

print(left-(floor_sum(left, D, C, C+D//2)-floor_sum(left, B, A, A+B//2)))
0