結果
問題 | No.2896 Monotonic Prime Factors |
ユーザー | ねしん |
提出日時 | 2024-09-20 22:21:13 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 634 ms / 2,000 ms |
コード長 | 1,445 bytes |
コンパイル時間 | 991 ms |
コンパイル使用メモリ | 84,848 KB |
実行使用メモリ | 29,952 KB |
最終ジャッジ日時 | 2024-09-20 22:21:25 |
合計ジャッジ時間 | 11,409 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 293 ms
29,796 KB |
testcase_01 | AC | 295 ms
29,752 KB |
testcase_02 | AC | 288 ms
29,756 KB |
testcase_03 | AC | 315 ms
29,948 KB |
testcase_04 | AC | 634 ms
29,952 KB |
testcase_05 | AC | 552 ms
29,864 KB |
testcase_06 | AC | 513 ms
29,824 KB |
testcase_07 | AC | 628 ms
29,952 KB |
testcase_08 | AC | 617 ms
29,824 KB |
testcase_09 | AC | 555 ms
29,824 KB |
testcase_10 | AC | 450 ms
29,916 KB |
testcase_11 | AC | 330 ms
29,756 KB |
testcase_12 | AC | 311 ms
29,824 KB |
testcase_13 | AC | 466 ms
29,824 KB |
testcase_14 | AC | 502 ms
29,724 KB |
testcase_15 | AC | 324 ms
29,952 KB |
testcase_16 | AC | 361 ms
29,952 KB |
testcase_17 | AC | 324 ms
29,868 KB |
testcase_18 | AC | 592 ms
29,824 KB |
testcase_19 | AC | 323 ms
29,800 KB |
ソースコード
#include <iostream> #include <vector> #include <cmath> using namespace std; const int MAXN = 17 * 100000 + 1; const int MOD = 998244353; vector<long long> fact(MAXN, 1), invfact(MAXN, 1); // 素因数分解して因数の数を返す関数 int factorize(int A) { int c = 0; int M = A; for (int i = 2; i <= sqrt(A) + 2; i++) { if (M < i) break; while (M % i == 0) { M /= i; c++; } } if (M != 1) c++; return c; } // 組み合わせC(n, r)を計算する関数 long long C(int n, int r) { return fact[n] * invfact[r] % MOD * invfact[n - r] % MOD; } // 繰り返し二乗法による累乗計算 (mod MOD) long long mod_pow(long long base, long long exp, long long mod) { long long result = 1; while (exp > 0) { if (exp % 2 == 1) result = result * base % mod; base = base * base % mod; exp /= 2; } return result; } int main() { // 階乗と階乗の逆元を事前に計算 for (int i = 2; i < MAXN; i++) { fact[i] = fact[i - 1] * i % MOD; invfact[i] = invfact[i - 1] * mod_pow(i, MOD - 2, MOD) % MOD; } int Q; cin >> Q; int cnt; cnt=0; while (Q--) { int a, b; cin >> a >> b; cnt = cnt+factorize(a); if (cnt < b) { cout << 0 << endl; continue; } cout << C(cnt - 1, cnt - b) << endl; } return 0; }