結果

問題 No.3118 Increment or Multiply
コンテスト
ユーザー Naru820
提出日時 2025-11-19 09:19:44
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 31 ms / 2,000 ms
コード長 2,442 bytes
コンパイル時間 717 ms
コンパイル使用メモリ 80,048 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-11-19 11:11:15
合計ジャッジ時間 2,793 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**
 * 問題: C=K から C=N にするための最小操作回数の総和
 * 操作: +1 または *A
 * * 解法:
 * 逆から考える再帰構造を利用します。
 * M = floor(N / A) とすると、
 * 1. K > M の場合: A倍するとNを超えるため、+1のみで到達するしかない。
 * コストは N - K。
 * 2. K <= M の場合: Mまで到達してからA倍し、残りを+1するのが最適。
 * コストは f(K, M) + 1 + (N % A)。
 * * これにより、S(N) = S(M) + M*(1 + N%A) + (M+1からNまでの単純和) となる。
 * 計算量は O(log N)。
 * gemini 3-pro
 */

#include <iostream>

using namespace std;

long long MOD = 998244353;
long long INV2 = 499122177; // 2の逆元 (mod 998244353)

// 0 から k-1 までの総和 k*(k-1)/2 を mod で計算
long long sum_0_to_k_minus_1(long long k) {
    if (k <= 0) return 0;
    long long term1 = k % MOD;
    long long term2 = (k - 1) % MOD;
    long long res = term1 * term2 % MOD;
    return res * INV2 % MOD;
}

long long solve(long long n, long long a) {
    if (n == 0) return 0;
    
    // A=1の場合は掛け算の意味がないため、全て+1で到達するしかない
    // K=1..N それぞれについて N-K 回の操作
    // 総和は sum_{i=1}^{N} (N-i) = sum_{j=0}^{N-1} j = N(N-1)/2
    if (a == 1) {
        return sum_0_to_k_minus_1(n);
    }

    // A > N の場合、一度も掛け算できないので A=1 と同じ扱い
    if (n < a) {
        return sum_0_to_k_minus_1(n);
    }

    long long m = n / a;
    long long rem = n % a;

    // 1. K > M の部分 (掛け算なし)
    // 区間の長さは N - M
    // コストの総和は 0 + 1 + ... + (N - M - 1)
    long long part1 = sum_0_to_k_minus_1(n - m);

    // 2. K <= M の部分 (再帰 + 追加コスト)
    // S(M)
    long long recursive_part = solve(m, a);
    
    // 各要素に加算される定数コスト: 1 (掛け算) + rem (あまりの足し算)
    long long constant_cost = (1 + rem) % MOD;
    // これが M 個分ある
    long long part2_constant = (m % MOD) * constant_cost % MOD;

    long long total = (part1 + recursive_part + part2_constant) % MOD;
    return total;
}

void solve_case() {
    long long N, A;
    cin >> N >> A;
    cout << solve(N, A) << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    cin >> T;
    while (T--) {
        solve_case();
    }
    return 0;
}
0