結果

問題 No.3118 Increment or Multiply
コンテスト
ユーザー nu
提出日時 2025-04-20 12:25:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,483 bytes
コンパイル時間 1,809 ms
コンパイル使用メモリ 198,008 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-20 12:25:58
合計ジャッジ時間 3,239 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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) {
    long long n_mod = N % M;
    if (A == 1) {
        return n_mod * ((N - 1) % M) % M * INV2 % M;
    }

    // B[m] = A^m
    vector<unsigned long long> B;
    B.reserve(64);
    u128 p = 1;
    while (p <= (u128)N) {
        B.push_back((unsigned long long)p);
        p = p * A;
    }
    int L = B.size();

    // r[m] = floor(N / B[m])
    vector<unsigned long long> r(L + 1);
    for (int i = 0; i < L; i++) r[i] = N / B[i];
    r[L] = 0;

    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];
        long long Kmod = K % M;
        // sum of k from l to rr
        long long sum_k = ((l + rr) % M) * Kmod % M * INV2 % M;

        long long term1 = (long long)i % M * Kmod % M;
        long long term2 = n_mod * Kmod % M;
        long long Bmod = B[i] % M;
        long long term3 = Bmod * sum_k % M;

        ans = (ans + term1 + term2 - term3) % M;
    }
    if (ans < 0) ans += 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