結果

問題 No.3559 +A,-B
コンテスト
ユーザー GOTKAKO
提出日時 2026-05-29 21:56:52
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 63 ms / 2,000 ms
コード長 1,703 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,489 ms
コンパイル使用メモリ 215,576 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-05-29 21:56:59
合計ジャッジ時間 5,773 ms
ジャッジサーバーID
（参考情報） 		judge4_1 / judge1_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 10 % AC * 4
部分点2 60 % AC * 7
部分点3 30 % AC * 20
合計 100 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while(T--){
        long long N,X,Y,A,B; cin >> N >> X >> Y >> A >> B;
        bool end = false;
        auto f = [&]() -> pair<long long,long long> {
            if(X+Y >= 0){
                end = B<=0;
                return {X,Y-B};
            }    
            else{
                end = A<=0;
                return {X+A,Y};
            }    
        };
        auto ans = [&]() -> void {cout << X << " " << Y << "\n";};
        tie(X,Y) = f(),N--;
        if(end || N == 0){
            if(X+Y >= 0) Y -= B*N;
            else X += A*N;
            ans(); continue;
        }
        if(X+Y >= 0){
            long long ope = (X+Y+1+B-1)/B;
            ope = min(ope,N);
            Y -= B*ope,N -= ope;
        }
        else{
            long long ope = (-(X+Y)+A-1)/A;
            ope = min(ope,N);
            X += A*ope,N -= ope;
        }
        if(N == 0){ans(); continue;}
        tie(X,Y) = f(),N--;
        if(end || N == 0){
            if(X+Y >= 0) Y -= B*N;
            else X += A*N;
            ans(); continue;
        }

        long long g = gcd(abs(A),abs(B)),lcm = abs(A*B)/g,cycle = lcm/A+lcm/B;
        long long loop = N/cycle;
        X += lcm*loop,Y -= lcm*loop;
        N %= cycle;

        long long low = -1,high = N+1;
        while(high-low > 1){
            long long mid = (high+low)/2;
            long long dec = mid,add = N-mid;
            long long now = X+Y+add*A-dec*B;
            if(now >= A) low = mid;
            else high = mid;
        }
        Y -= high*B,X += (N-high)*A;
        ans(); 
    }
}
0