結果

問題 No.3118 Increment or Multiply
コンテスト
ユーザー AKI
提出日時 2025-04-20 13:29:04
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 98 ms / 2,000 ms
コード長 3,210 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,378 ms
コンパイル使用メモリ 200,856 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-20 13:29:09
合計ジャッジ時間 5,173 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using i128 = __int128_t;
const long long MOD = 998244353LL;

// 128→64 の安全な剰余
static inline long long mod128(i128 x) {
    long long r = (long long)(x % MOD);
    if (r < 0) r += MOD;
    return r;
}

// 最下位 (m = 0) のコスト = そのまま差分
static i128 costDigits(i128 R, int m, const vector<i128>& powA, i128 A) {
    if (m == 0) return R;          // ただ足すだけ
    i128 res = 0, rem = R;
    for (int p = m; p >= 1; --p) { // A^p, A^(p-1), ...
        i128 div = powA[p];
        i128 q = rem / div;
        res += q;
        rem -= q * div;
    }
    return res + rem;              // 最下位桁
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;  cin >> T;
    const i128 iMOD = MOD;
    const i128 INV2 = (MOD + 1) / 2;   // 2 の逆元

    while (T--) {
        long long Nll, All; cin >> Nll >> All;
        i128 N = Nll, A = All;

        // A = 1 もしくは A > N : 加算しか無い
        if (A == 1 || A > N) {
            i128 n = N % iMOD;
            i128 ans = n * ((N - 1) % iMOD) % iMOD;
            ans = ans * INV2 % iMOD;
            cout << (long long)ans << '\n';
            continue;
        }

        /* --- 前処理: A^m 一覧 (0 〜 M) --- */
        vector<i128> powA{1};          // A^0
        while (powA.back() <= N / A)   // 次のべき乗がまだ N 以下
            powA.push_back(powA.back() * A);
        int M = (int)powA.size() - 1;  // 最大 m s.t. A^m ≤ N

        /* --- Q_m, L_m を構築 --- */
        vector<i128> Q, L;
        i128 pow = 1;
        for (int m = 0; ; ++m) {
            i128 Qm = N / pow;
            if (Qm == 0) break;

            i128 Lm;
            if (m == 0) Lm = N;                      // 加算のみ
            else {
                i128 R = N % pow;
                i128 cost = costDigits(R, m - 1, powA, A);
                Lm = m + Qm + cost;
            }
            Q.push_back(Qm);
            L.push_back(Lm);

            if (pow > N / A) break;  // 次で Q=0
            pow *= A;
        }
        const int SZ = (int)Q.size();

        /* --- 区間ごとの最小切片 (prefix‑min) --- */
        vector<i128> pref(SZ);
        i128 best = (i128)4e36;      // 十分大きい値
        for (int i = 0; i < SZ; ++i) {
            if (L[i] < best) best = L[i];
            pref[i] = best;
        }

        /* --- 区間和を足し込む --- */
        long long ans = 0;
        for (int i = 0; i + 1 < SZ; ++i) {
            i128 high = Q[i], low = Q[i + 1];
            i128 cnt = high - low;
            if (!cnt) continue;
            i128 Lmin = pref[i];
            i128 sumK = high * (high + 1) / 2 - low * (low + 1) / 2;
            i128 term = cnt * Lmin - sumK;
            ans += mod128(term);
            if (ans >= MOD) ans -= MOD;
        }
        // 最後の区間 (0, Q_back]
        {
            i128 high = Q.back();
            i128 Lmin = pref.back();
            i128 cnt = high;
            i128 term = cnt * Lmin - high * (high + 1) / 2;
            ans += mod128(term);
            ans %= MOD;
        }
        cout << ans << '\n';
    }
    return 0;
}
0