結果

問題 No.3398 Accuracy of Integer Division Approximate Function 2
コンテスト
ユーザー to-omer
提出日時 2025-12-06 01:01:44
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,462 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 205 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 18,216 KB
最終ジャッジ日時 2025-12-06 01:02:03
合計ジャッジ時間 3,998 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# A * x + B * (C * x + D) // M + E
def yuki3397(N, M, A, B, C, D, E=0):
    if N == 0:
        return -(2**256)
    assert M > 0
    C0, C = divmod(C, M)
    A += B * C0
    D0, D = divmod(D, M)
    E += B * D0
    f = lambda x: A * x + B * ((C * x + D) // M) + E
    if A >= 0 and B >= 0 or A <= 0 and B <= 0 or C == 0 or N <= 2:
        return max(f(0), f(N - 1))
    if A > 0 and B < 0:
        return max(yuki3397((C * (N - 1) + D) // M, C, B, A, M, M - D - 1, E), f(N - 1))
    if A < 0 and B > 0:
        return max(
            yuki3397((C * (N - 1) + D) // M, C, B, A, M, M + C - D - 1, B + E), f(0)
        )


# min x. x // D - (x // A) * (A * B // D) // B > K
# x = y * D
# M = A * B // D
# x // D - (x // A) * M // B > K
# y - (D * y // A) * M // B > K
# B * y - M * (D * y // A) > K * B
def solve(D, A, B, K, Y):
    return yuki3397(Y, A, B, -(A * B // D), D, 0) <= K * B


def main():
    T = int(input())
    for _ in range(T):
        D, A, B, K = map(int, input().split())

        def check(x):
            return solve(D, A, B, K, x)

        ok = 0
        ng = 1
        while check(ng):
            ng *= 2
            if ng > 2**256:
                break
        while ng - ok > 1:
            mid = (ok + ng) // 2
            if check(mid):
                ok = mid
            else:
                ng = mid

        if not check(ng):
            print(ok * D)
        else:
            print(-1)


if __name__ == "__main__":
    main()
0