結果

問題 No.3397 Max Weighted Floor of Linear
コンテスト
ユーザー GOTKAKO
提出日時 2025-12-04 04:50:08
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 673 ms / 2,000 ms
コード長 4,715 bytes
記録
コンパイル時間 2,533 ms
コンパイル使用メモリ 203,720 KB
実行使用メモリ 7,840 KB
最終ジャッジ日時 2025-12-04 04:50:21
合計ジャッジ時間 12,468 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

struct Minmod{long long x,q,len;}; //[x,x+q,x+2*q,...,x+(len-1)*q] O(logm)の等差数列で済む.
vector<Minmod> MinofModLinear(long long a,long long b,long long m){ //min(a*x+b modM)を更新するxを返す.
    assert(0 < m && m <= numeric_limits<int>::max()); //mod*modの計算が必要.
    a %= m,b %= m,a += m,b += m;
    a = a>=m?a-m:a,b = b>=m?b-m:b; //a,bをmodMに.
    vector<Minmod> ret = {{0,1,1}}; //X=0だけ特別.
    if(a == 0 || b == 0) return {{0,1,1}}; //a=0orb=0は当然x=0が最善.
    if(a) a = m-a; // a<=-aとして考える -ax+bのminを求める.
    long long X = 0,Y = b; //現在のx,y;
    if(a <= Y){ //q=1を処理.
        long long len = Y/a; Y %= a;
        ret.at(0) = {X,1,len+1};
        X += len;
    }
    long long p1 = 0,q1 = 1,p2 = 1,q2 = 0; //p1/q1<=a/m<=p2/q2.
    long long n = a,d = m; //n/dに近いp/qを探していく aq(modM)<=Yが欲しい.
    while(n){ //だいたいStern-Brocot木  aq-mp<=Yとして考える.
        long long move = d/n; d %= n; //p2/q2を更新.
        p2 += p1*move,q2 += q1*move;
        if(d == 0) break;
        move = n/d; n %= d;
        if(move > 0){
            long long np = p1+p2*move,nq = q1+q2*move; //次のp1/q1.
            long long c1 = a*q1-m*p1,c2 = a*q2-m*p2,c3 = a*nq-m*np; //a/m>=p1/q1の変形 aq-mpになる.
            
            while(c3 <= Y){ //np/nqで更新の場合.
                long long t = max(0LL,(c1-Y+(-c2)-1)/(-c2)); //Yを超えないだけ進む.
                if(c1+c2*t == 0) break; //a/mと一致した場合.
                long long dx = q1+q2*t,dy = c1+c2*t; //dyの値が欲しいやつになる aq modm<=Y.
                long long len = Y/dy; Y %= dy;
                ret.push_back({X+dx,dx,len});
                X += dx*len;
            }
            p1 = np,q1 = nq; //p1/q1を更新.
        }
    }
    return ret;
}
vector<long long> MinofModLinear(long long N,long long M,long long a,long long b){ //0<=x<Nでmin(ax+b modM)を返す.
    assert(0 < N && 0 < M && max(a,b) < M);
    long long X = 0;
    vector<long long> ret;
    for(auto [x,q,len] : MinofModLinear(a,b,M)){
        if(N <= x) break;
        long long r = x+q*(len-1);
        ret.push_back(x);
        if(r < N){ret.push_back(r); continue;}
        long long add = (N-1-x)/q;
        ret.push_back(x+add*q);
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while(T--){
        long long N,M,A,B,C,D; cin >> N >> M >> A >> B >> C >> D;
        auto f = [&](long long x) -> long long {
            assert(0 <= x && x < N);
            return A*x+B*((C*x+D)/M);
        };
        //long long g = gcd(M,C);
        //D = D/g*g;
        //D /= g,C /= g,M /= g;        
        //
        long long best = -1;
        vector<long long> BestX;
        if(false){
            for(int i=0; i<N; i++){
                long long now = f(i);
                if(now > best) BestX = {i},best = now;
                else if(now == best) BestX.push_back(i);    
            }
        }

        if(A <= 0 && B <= 0) cout << f(0) << "\n";
        else if(A >= 0 && B >= 0) cout << f(N-1) << "\n";
        else if(A >= 0 && B <= 0){
            if(A+B >= 0) cout << f(N-1) << "\n";
            else{
                D = M-1-D,C = (M-C)%M;
                long long answer = 0,type = A*M+B*C;
            
                D = (C*(N-1)+D)%M,C = (M-C)%M;
                for(auto x : MinofModLinear(N,M,C,D)){
                    C = (M-C)%M,D = (D-C*(N-1)%M+M)%M;
                    D = M-1-D,C = (M-C)%M;
                    answer = max(answer,f(N-1-x));
                    D = M-1-D,C = (M-C)%M;
                    D = (C*(N-1)+D)%M,C = (M-C)%M;
                }
                D = (C*(N-1)+D)%M,C = (M-C)%M;
                for(auto x : MinofModLinear(N,M,C,D)){
                    D = M-1-D,C = (M-C)%M;
                    answer = max(answer,f(x)); 
                    D = M-1-D,C = (M-C)%M;
                }    
                cout << answer << "\n";
            }
        }
        else{
            if(A+B <= 0) cout << f(0) << "\n";
            else{
                long long answer = 0;
                D = (C*(N-1)+D)%M,C = (M-C)%M;
                for(auto x : MinofModLinear(N,M,C,D)){
                    C = (M-C)%M,D = (D-C*(N-1)%M+M)%M;
                    answer = max(answer,f(N-1-x));
                    D = (C*(N-1)+D)%M,C = (M-C)%M;
                }    
                D = (C*(N-1)+D)%M,C = (M-C)%M;
                for(auto x : MinofModLinear(N,M,C,D)) answer = max(answer,f(x)); 
                cout << answer << "\n";
            }
        }
    }
}
0