結果

問題 No.2818 A Game I Play to Pass the Time
コンテスト
ユーザー vjudge1
提出日時 2026-03-23 11:22:23
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 178 ms / 2,000 ms
コード長 1,895 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,445 ms
コンパイル使用メモリ 212,368 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-03-23 11:22:36
合計ジャッジ時間 9,879 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
vector<int> primes = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
long long fact[61], inv_fact[61];

long long pow_mod(long long a, long long b, long long mod) {
    long long res = 1;
    while (b > 0) {
        if (b % 2 == 1) res = res * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return res;
}

void precompute() {
    fact[0] = 1;
    for (int i=1; i<=60; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    inv_fact[60] = pow_mod(fact[60], MOD-2, MOD);
    for (int i=59; i>=0; i--) {
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    precompute();
    int T;
    cin >> T;
    while (T--) {
        long long N, S;
        cin >> N >> S;
        long long mod_S = S % MOD;
        if (mod_S == 0) {
            cout << "0\n";
            continue;
        }
        long long t_mod = (mod_S - 1 + MOD) % MOD;
        long long comb[61];
        comb[0] = 1;
        long long prod = 1;
        for (int m=1; m<=60; m++) {
            prod = prod * (t_mod + m - 1) % MOD;
            comb[m] = prod * inv_fact[m] % MOD;
        }
        long long temp = N;
        long long ans = 1;
        for (int p : primes) {
            if (temp == 1) break;
            if (temp % p!= 0) continue;
            int e = 0;
            while (temp % p == 0) {
                e++;
                temp /= p;
            }
            long long sum_p = 0;
            long long p_pow = 1;
            for (int k=0; k<=e; k++) {
                int m = e - k;
                sum_p = (sum_p + p_pow * comb[m]) % MOD;
                p_pow = p_pow * p % MOD;
            }
            ans = ans * sum_p % MOD;
        }
        ans = ans * mod_S % MOD;
        cout << ans << '\n';
    }
    return 0;
}
0