結果

問題 No.3397 Max Weighted Floor of Linear
コンテスト
ユーザー 👑 Mizar
提出日時 2025-11-15 06:28:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 204 ms / 2,000 ms
コード長 3,425 bytes
記録
コンパイル時間 501 ms
コンパイル使用メモリ 69,112 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-12-03 23:32:39
合計ジャッジ時間 5,636 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <cassert> // assert
#include <iostream> // cin, cout, ios
#include <utility> // swap, pair

template <typename T>
constexpr std::pair<T, T> divmod(T a, T b) {
    T q = a / b;
    T r = a % b;
    return {q, r};
}

// 商を無限大方向に切り下げる除算(剰余が0でない時の符号は除数の符号に一致)
template <typename T>
constexpr std::pair<T, T> floor_divmod(T a, T b) {
    // 標準の truncating 除算を使う
    T q = a / b;
    T r = a % b;
    // もし符号が食い違っていたら 1 調整
    if ((r != 0) && ((r > 0) != (b > 0))) {
        q -= 1;
        r += b;
    }
    return {q, r};
}

// 剰余が非負になる除算（ユークリッド除算）
template <typename T>
constexpr std::pair<T, T> euclid_divmod(T a, T b) {
    // 標準の truncating 除算を使う
    T q = a / b;
    T r = a % b;
    // 剰余が負なら 1 調整
    if (r < 0) {
        if (b > 0) {
            q -= 1;
            r += b;
        } else {
            q += 1;
            r -= b;
        }
    }
    return {q, r};
}

/**
    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, 0 <= c < m, 0 <= d < m

    計算量/メモリ:
      - 時間: O(log m)（ユークリッド互除法的再帰による構造縮約）
      - 追加メモリ: O(1)
*/
template<typename T>
T mwf(T n, T m, T a, T b, T c, T d) {
    assert(n > 0 && m > 0);
    // c, d を m で割った余りに変換し、a, b を更新
    const auto divmod_c = euclid_divmod(c, m);
    c = divmod_c.second;
    a = a + b * divmod_c.first;
    const auto divmod_d = euclid_divmod(d, m);
    d = divmod_d.second;
    T sum_acc = b * divmod_d.first;
    T max_acc = sum_acc;
    while(true) {
        assert(0 <= c && c < m && 0 <= d && d < m);
        // 0 ≤ x < n における y = floor((c*x+d)/m) の最大値 y_max を計算
        const T y_max = (c * (n - 1) + d) / m; // y_max >= 0
        // 現在の小問題における x = 0, n-1 のときの値を max_acc に反映
        const T rval = sum_acc + a * (n - 1) + b * y_max;
        if(max_acc < sum_acc) {
            max_acc = sum_acc;
        }
        if(max_acc < rval) {
            max_acc = rval;
        }
        // x = 0, n-1 のいずれかで最大値を取るのが確定したら終了
        if(y_max == 0 || a == 0 || b == 0 || (a > 0 && b > 0) || (a < 0 && b < 0)) {
            return max_acc;
        }
        // 小問題へのパラメータ変換
        if(a < 0) {
            sum_acc += a + b;
        }
        n = y_max;
        d = m - d - 1;
        std::swap(a, b);
        std::swap(c, m);
        assert(0 < n && 0 < m && 0 <= c && 0 <= d);
        // c, d を m で割った余りに変換し、a, b, sum_acc を更新
        const std::pair<T, T> divmod_c = divmod(c, m);
        c = divmod_c.second;
        a = a + b * divmod_c.first;
        const std::pair<T, T> divmod_d = divmod(d, m);
        d = divmod_d.second;
        sum_acc = sum_acc + b * divmod_d.first;
    }
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int t;
    long n, m, a, b, c, d, ans;
    std::cin >> t;
    for(int i = 0; i < t; i++) {
        std::cin >> n >> m >> a >> b >> c >> d;
        assert(n > 0 && m > 0);
        ans = mwf(n, m, a, b, c, d);
        std::cout << ans << '\n';
    }
}
0