結果
問題 | No.2896 Monotonic Prime Factors |
ユーザー |
👑 |
提出日時 | 2024-09-12 16:12:07 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 305 ms / 2,000 ms |
コード長 | 976 bytes |
コンパイル時間 | 3,132 ms |
コンパイル使用メモリ | 245,772 KB |
実行使用メモリ | 9,728 KB |
最終ジャッジ日時 | 2024-09-12 16:12:15 |
合計ジャッジ時間 | 7,093 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/modint>using namespace std;using namespace atcoder;using mint = modint998244353;mint factorial[1600000];void init_factorial() {factorial[0] = 1;for (int i = 1; i < 1600000; i++) {factorial[i] = factorial[i - 1] * i;}}mint comb(int n, int r) {if (n < r) {return mint(0);}return factorial[n] / (factorial[r] * factorial[n - r]);}int count_prime(int n) {int count = 0;while (n % 2 == 0) {n /= 2;count++;}for (int i = 3; i * i <= n; i += 2) {while (n % i == 0) {n /= i;count++;}}if (n > 1) {count++;}return count;}int main() {init_factorial();int Q;cin >> Q;int count = 0;while (Q--) {int A, B;cin >> A >> B;count += count_prime(A);cout << comb(count - 1, B - 1).val() << endl;}}