結果

問題 No.3397 Max Weighted Floor of Linear
コンテスト
ユーザー 👑 Mizar
提出日時 2025-11-12 08:49:09
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 548 ms / 2,000 ms
コード長 3,745 bytes
記録
コンパイル時間 1,488 ms
コンパイル使用メモリ 81,768 KB
実行使用メモリ 78,384 KB
最終ジャッジ日時 2025-12-03 23:31:31
合計ジャッジ時間 10,606 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# -*- coding: utf-8 -*-
"""
Max Weighted Floor (mwf) を求める。
"""


def mwf(n: int, m: int, a: int, b: int, c: int, d: int) -> int:
    """
    Max Weighted Floor (mwf) の非再帰実装。
      mwf(n,m,a,b,c,d) = max_{0 <= x < n} a*x + b*floor((c*x + d)/m)

    前提:
      - n > 0, m > 0

    計算量/メモリ:
      - 時間: O(log m)（ユークリッド互除法的再帰による構造縮約）
      - 追加メモリ: O(1)
    """
    assert n > 0 and m > 0
    sum_acc: int = int(0)  # 現在の累積和
    max_acc: int = b * (d // m)  # 現在の累積max. 初期値は x = 0 のときの値
    while True:
        # c, d をそれぞれ 正の整数 m で割った剰余にする正規化
        # Python の divmod は Flooring Division に基づくので、除数 m が正であるため
        # 元の c, d が負でも正規化後の剰余は 0 <= c < m, 0 <= d < m が保証される
        # 負の整数 % 正の整数 = 負の整数 となる言語（C++/Java など）では移植時に注意
        q, c = divmod(c, m)  # q = c // m, c = c % m
        a += b * q  # c の商分を a に足す
        q, d = divmod(d, m)  # q = d // m, d = d % m
        sum_acc += b * q  # d の商分を s に足す
        assert 0 <= c < m and 0 <= d < m
        # 現在の小問題における x = 0 のときの値 s を r に反映
        max_acc = max(max_acc, sum_acc)
        # 0 ≤ x < n における y = floor((c*x+d)/m) の最大値を計算
        y_max = (c * (n - 1) + d) // m
        # y_max == 0 もしくは　a,bともに非負 の場合は右端を考慮して終了
        if y_max == 0:
            return max(max_acc, sum_acc + a * (n - 1))
        # y_max >= 1 の場合は再帰的に解く
        # c > 0, n > 1 のときにのみ y_max >= 1 となりうる
        if a > 0:
            # a > 0 の場合
            max_acc = max(max_acc, sum_acc + a * (n - 1) + b * y_max)
            if b >= 0:
                # a,b >= 0 の場合は右端で最大値が確定するので終了
                return max_acc
        else:
            if b <= 0:
                # a,b <= 0 の場合はこれ以上増加しないので終了
                return max_acc
            # a < 0 の場合
            sum_acc += a + b
        # 小問題へのパラメータ変換
        n, m, a, b, c, d = y_max, c, b, a, m, (m - d - 1)


def mwf_lr(L: int, R: int, m: int, a: int, b: int, c: int, d: int) -> int:
    """
    max_{L <= x < R} a*x + b*floor((c*x + d)/m) を計算して返す。

    既存の mwf(n, m, a, b, c, d)（0 <= x < n）を用いる。
    前提: L < R, m > 0
    計算量: 既存の mwf に準ずる（O(log m) スタイルの再帰）。
    """
    assert L < R and m > 0
    n = R - L
    q, d = divmod(c * L + d, m)
    return a * L + b * q + mwf(n, m, a, b, c, d)


def min_of_mod_of_linear(n: int, m: int, a: int, b: int) -> int:
    """
    min_{0 <= x < n} ( (a*x + b) % m ) を計算して返す。

    (a*x + b) % m
      = a*x + b - m * floor((a*x + b)/m)
      = b - ( -a*x + m*floor((a*x + b)/m) )

    これは b - mwf(n, m, -a, m, a, b) を求める問題に帰着する。
    前提: n > 0, m > 0
    https://judge.yosupo.jp/problem/min_of_mod_of_linear
    """
    assert n > 0 and m > 0
    return b - mwf(n, m, -a, m, a, b)


def solve():
    """
    入力を受け取り、各ケースについて mwf(N, M, A, B, C, D) を求めて出力します。
    """
    import sys
    input = sys.stdin.readline

    T = int(input())
    for _ in range(T):
        N, M, A, B, C, D = map(int, input().split())
        assert 1 <= N
        assert 1 <= M
        ans = mwf(N, M, A, B, C, D)
        print(ans)


if __name__ == '__main__':
    solve()
0