結果

問題 No.3118 Increment or Multiply
コンテスト
ユーザー nu
提出日時 2025-04-20 12:23:40
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,592 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,183 ms
コンパイル使用メモリ 197,696 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-20 12:23:44
合計ジャッジ時間 4,114 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 25 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using u128 = unsigned __int128;

const long long M = 998244353;
const long long INV2 = (M + 1) / 2;

long long solve(long long N, long long A) {
    if (A == 1) {
        long long nm = N % M;
        return nm * ((N - 1) % M) % M * INV2 % M;
    }

    vector<unsigned long long> B;
    vector<unsigned long long> r;
    u128 p = 1;
    while (p <= (u128)N) {
        B.push_back((unsigned long long)p);
        p = p * A;
    }
    int L = B.size();
    r.resize(L + 1);
    for (int i = 0; i < L; i++) {
        r[i] = N / B[i];
    }
    r[L] = 0;

    vector<unsigned long long> C(L);
    for (int i = 0; i < L; i++) {
        // C_i = i + N - r_i * B[i] + r_i
        C[i] = (unsigned long long)(i) + N - r[i] * B[i] + r[i];
    }
    vector<unsigned long long> D(L);
    D[0] = C[0];
    for (int i = 1; i < L; i++) {
        D[i] = min(D[i - 1], C[i]);
    }

    long long ans = 0;
    for (int i = 0; i < L; i++) {
        unsigned long long l = r[i + 1] + 1;
        unsigned long long rr = r[i];
        if (l > rr) continue;
        unsigned long long K = rr - r[i + 1];
        // sum_k = (l + rr) * K / 2 mod M
        long long sum_k = ( (l + rr) % M ) * (K % M) % M * INV2 % M;
        long long contrib = ( (D[i] % M) * (K % M) % M - sum_k + M ) % M;
        ans = (ans + contrib) % M;
    }
    return ans;
}

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

    int T;
    cin >> T;
    while (T--) {
        long long N, A;
        cin >> N >> A;
        cout << solve(N, A) << "\n";
    }
    return 0;
}
0