結果

問題 No.3118 Increment or Multiply
ユーザー AKI
提出日時 2025-04-20 13:16:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,315 bytes
コンパイル時間 2,201 ms
コンパイル使用メモリ 195,172 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-20 13:16:50
合計ジャッジ時間 3,998 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using i128  = __int128_t;
const int64 MOD = 998244353;
const int64 INV2 = 499122177;          // 2^{-1} mod MOD

// a*b mod MOD (a,b < MOD)
inline int64 mul_mod(i128 a, i128 b) {
    return (int64)((a * b) % MOD);
}

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

    int T;  cin >> T;
    while (T--) {
        uint64_t N, A;   // N, A ≤ 1e18
        cin >> N >> A;

        int64 Nmod = N % MOD;
        int64 answer = 0;

        if (A == 1) {
            // N*(N-1)/2 mod MOD
            answer = mul_mod(Nmod, (Nmod + MOD - 1) % MOD);
            answer = mul_mod(answer, INV2);
            cout << answer << '\n';
            continue;
        }

        uint64_t M = N / A;          // floor(N/A)
        uint64_t len_big = N - M;    // 区間 (M, N]

        // 三角数パート
        int64 lenb_mod = len_big % MOD;
        answer = mul_mod(lenb_mod, (lenb_mod + MOD - 1) % MOD);
        answer = mul_mod(answer, INV2);           // len*(len-1)/2

        // ループで「掛け算→境界を超える直前の K 範囲」を処理
        uint64_t cur_high = M;
        int64  Apow_mod = A % MOD;   // A^t  (t = 1 から始める)
        int    t = 1;

        while (cur_high) {
            uint64_t next_high = cur_high / A;      // ⌊cur/A⌋
            uint64_t len      = cur_high - next_high;   // 区間長
            uint64_t low      = next_high + 1;
            uint64_t high     = cur_high;

            // ΣK  = (low + high) * len / 2  （mod 計算）
            int64 sumK_mod = mul_mod( ( (low % MOD) + (high % MOD) ) % MOD,
                                      (len  % MOD) );
            sumK_mod = mul_mod(sumK_mod, INV2);

            // ① +1,+1,… 部：len * t
            answer = (answer + mul_mod(len % MOD, t % MOD)) % MOD;
            // ② N を足す部：N * len
            answer = (answer + mul_mod(Nmod, len % MOD)) % MOD;
            // ③ 掛け算側：-A^t * ΣK
            answer = (answer - mul_mod(Apow_mod, sumK_mod) + MOD) % MOD;

            // 次の階層へ
            cur_high  = next_high;
            t++;
            Apow_mod  = mul_mod(Apow_mod, A % MOD);   // A^t mod MOD
        }

        cout << answer << '\n';
    }
    return 0;
}
0