結果

問題 No.3398 Accuracy of Integer Division Approximate Function 2
コンテスト
ユーザー NyaanNyaan
提出日時 2025-12-05 01:15:47
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 3,161 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 9,636 ms
コンパイル使用メモリ 431,788 KB
実行使用メモリ 15,940 KB
最終ジャッジ日時 2025-12-05 01:16:01
合計ジャッジ時間 10,634 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// 翻訳元：https://yukicoder.me/submissions/1138660
// translated by ChatGPT 5.1

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;
using Int = cpp_int;

// sum_{i=0}^{n-1} floor((a*i + b) / m)
Int floor_sum(Int n, Int m, Int a, Int b) {
    Int ans = 0;

    if (a < 0) {
        Int a2 = a % m + ((a % m) < 0 ? m : 0);
        Int cnt = n * (n - 1) / 2;
        ans -= cnt * ((a2 - a) / m);
        a = a2;
    }
    if (b < 0) {
        Int b2 = b % m + ((b % m) < 0 ? m : 0);
        ans -= n * ((b2 - b) / m);
        b = b2;
    }
    if (a >= m) {
        Int cnt = (n - 1) * n / 2;
        ans += cnt * (a / m);
        a %= m;
    }
    if (b >= m) {
        ans += n * (b / m);
        b %= m;
    }

    Int y_max = (a * n + b) / m;
    Int x_max = y_max * m - b;
    if (y_max == 0) return ans;

    ans += (n - (x_max + a - 1) / a) * y_max;
    ans += floor_sum(y_max, a, m, (a - x_max % a) % a);
    return ans;
}

// sum_{i=nL}^{nR-1} floor((a*i + b) / m)
Int fs(Int nL, Int nR, Int m, Int a, Int b) {
    return floor_sum(nR, m, a, b) - floor_sum(nL, m, a, b);
}

Int between(Int N,
            Int a1, Int b1, Int m1,
            Int a2, Int b2, Int m2) {
    auto on = [&](const Int& x) -> bool {
        // (a1*x + b1)/m1 > (a2*x + b2)/m2
        return (a1 * x + b1) * m2 > (a2 * x + b2) * m1;
    };

    Int nL = 0, nR = N;

    // 左側: on(x) が最初に true になる点
    if (!on(nL)) {
        Int ng = nL, ok = nR;
        while (ng + 1 < ok) {
            Int x = (ng + ok) / 2;
            if (on(x)) ok = x;
            else       ng = x;
        }
        nL = ok;
    }

    // 右側: on(x) が最後に true になる点
    if (!on(nR)) {
        Int ok = nL, ng = nR;
        while (ok + 1 < ng) {
            Int x = (ok + ng) / 2;
            if (on(x)) ok = x;
            else       ng = x;
        }
        nR = ng;
    }

    return fs(nL, nR, m1, a1, b1) - fs(nL, nR, m2, a2, b2);
}

Int calc(Int D, Int A, Int B, Int K) {
    K += 1;
    Int C = A * B / D;
    if (C == 0) return K * D;

    struct Line {
        Int a, b, m;
    };

    Line L1{D, 0, A};
    Line L2{D, -A, A};
    Line L3{B, B * (-K + 1) - 1, C};
    Line L4{B, -B * K - 1, C};

    // INF = 10^50
    Int INF = 1;
    for (int i = 0; i < 50; i++) INF *= 10;

    Int ng = 0, ok = INF;
    while (ng + 1 < ok) {
        Int N = (ng + ok) / 2;

        Int n1 = between(N + 1, L1.a, L1.b, L1.m, L4.a, L4.b, L4.m);
        Int n2 = between(N + 1, L1.a, L1.b, L1.m, L3.a, L3.b, L3.m);
        Int n3 = between(N + 1, L2.a, L2.b, L2.m, L4.a, L4.b, L4.m);
        Int n4 = between(N + 1, L2.a, L2.b, L2.m, L3.a, L3.b, L3.m);

        Int num = n1 - n2 - n3 + n4;
        if (num > 0) ok = N;
        else         ng = N;
    }

    if (ok == INF) return Int(-1);
    return ok * D;
}

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

    int t = 1;
    if (!(cin >> t)) return 0;
    while (t--) {
        Int D, A, B, K;
        cin >> D >> A >> B >> K;
        Int ans = calc(D, A, B, K);
        cout << ans << '\n';
    }
    return 0;
}
0