結果

問題 No.3398 Accuracy of Integer Division Approximate Function 2
コンテスト
ユーザー 👑 Mizar
提出日時 2025-11-18 23:17:01
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 396 ms / 2,000 ms
コード長 1,533 bytes
記録
コンパイル時間 174 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2025-12-04 23:32:58
合計ジャッジ時間 3,999 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# (Python3/PyPy3): Compute xmin(D,A,B,K), return -1 if not exists
# Δ(D,A,B,x) = floor(x/D) - floor(floor(x/A) * floor(AB/D) / B)
# xmin(D,A,B,K) = min{x ∈ ℕ | K < Δ(D,A,B,x)}

def mwf(L: int, R: int, m: int, a: int, b: int, c: int, d: int) -> int:
    assert L < R and 0 < m
    n = R - L
    qd0, d = divmod(c * L + d, m)
    max_acc = sum_acc = a * L + b * qd0
    while True:
        qc, c = divmod(c, m)
        a += b * qc
        qd, d = divmod(d, m)
        sum_acc += b * qd
        y_max = (c * (n - 1) + d) // m
        max_acc = max(max_acc, sum_acc, sum_acc + a * (n - 1) + b * y_max)
        if y_max == 0 or (a >= 0 and b >= 0) or (a <= 0 and b <= 0):
            return max_acc
        if a < 0:
            sum_acc += a + b
        n, m, a, b, c, d = y_max, c, b, a, m, (m - d - 1)

def compute_xmin(D: int, A: int, B: int, K: int) -> int:
    import math 
    assert D > 0 and A > 0 and B > 0 and K >= 0
    gcd_DA = math.gcd(D, A)
    Dred, Ared, Tdelta = D // gcd_DA, A // gcd_DA, B * K
    Mred, Rred = divmod(Ared * B, Dred)
    if Rred == 0 and Dred * K + 1 >= Ared:
        return -1
    lo, hi = 0, Ared * B * K + 2
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if mwf(lo, mid, Ared, B, -Mred, Dred, 0) <= Tdelta:
            lo = mid
        else:
            hi = mid
    return D * lo

if __name__ == "__main__":
    import sys
    T = int(sys.stdin.readline())
    for _ in range(T):
        D, A, B, K = map(int, sys.stdin.readline().split())
        print(compute_xmin(D, A, B, K))
0