結果
問題 | No.2896 Monotonic Prime Factors |
ユーザー | porkleoi |
提出日時 | 2024-09-20 21:44:16 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,361 bytes |
コンパイル時間 | 3,245 ms |
コンパイル使用メモリ | 251,324 KB |
実行使用メモリ | 479,096 KB |
最終ジャッジ日時 | 2024-09-20 21:45:11 |
合計ジャッジ時間 | 20,954 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | TLE | - |
testcase_02 | TLE | - |
testcase_03 | TLE | - |
testcase_04 | TLE | - |
testcase_05 | TLE | - |
testcase_06 | TLE | - |
testcase_07 | TLE | - |
testcase_08 | TLE | - |
testcase_09 | TLE | - |
testcase_10 | TLE | - |
testcase_11 | TLE | - |
testcase_12 | TLE | - |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | TLE | - |
testcase_19 | TLE | - |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define rep2(i, s, n) for (ll i = s; i <= (ll)(n); i++) #define rep3(i, s, n, d) for (ll i = s; i <= (ll)(n); i += d) #define rep4(i, s, n, d) for (ll i = s; i >= (ll)(n); i += d) typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<vvi> vvvi; typedef vector<vvvi> vvvvi; typedef vector<string> vs; typedef vector<vs> vvs; typedef vector<vvs> vvvs; typedef vector<char> vc; typedef vector<vc> vvc; typedef vector<vvc> vvvc; typedef vector<ll> vll; typedef vector<vll> vvll; typedef vector<vvll> vvvll; typedef vector<vvvll> vvvvll; typedef vector<double> vd; typedef vector<vd> vvd; typedef vector<vvd> vvvd; typedef vector<ld> vld; typedef vector<vld> vvld; typedef vector<vvld> vvvld; typedef vector<bool> vb; typedef vector<vd> vvb; typedef vector<vvd> vvvb; typedef vector<pair<int, int>> vpi; typedef vector<pair<ll, ll>> vpll; typedef pair<int, int> pi; typedef vector<pi> vpi; typedef vector<vpi> vvpi; typedef pair<ll, ll> pll; typedef vector<pll> vpll; typedef vector<vpll> vvpll; typedef tuple<int, int, int> tui3; typedef tuple<ll, ll, ll> tull3; typedef priority_queue<int, vector<int>, greater<int>> pqi; typedef priority_queue<vi, vector<vi>, greater<vi>> pqvi; typedef priority_queue<ll, vector<ll>, greater<ll>> pqll; typedef priority_queue<vll, vector<vll>, greater<vll>> pqvll; typedef priority_queue<pll, vector<pll>, greater<pll>> pqpll; typedef priority_queue<pll, vector<pll>, less<pll>> rpqpll; typedef priority_queue<int, vector<int>, less<int>> rpqi; typedef priority_queue<vi, vector<vi>, less<vi>> rpqvi; typedef priority_queue<tui3, vector<tui3>, greater<tui3>> pqtui3; typedef priority_queue<tui3, vector<tui3>, less<tui3>> rpqtui3; typedef priority_queue<tull3, vector<tull3>, greater<tull3>> pqtull3; typedef priority_queue<tull3, vector<tull3>, less<tull3>> rpqtull3; #define yes(ans) if(ans)cout << "yes"<< endl; else cout << "no" << endl #define Yes(ans) if(ans)cout << "Yes"<< endl; else cout << "No" << endl #define YES(ans) if(ans)cout << "YES"<< endl ;else cout << "NO" << endl #define printv(vec) {rep(i, vec.size()) cout << vec[i] << ' '; cout << endl;} #define printvv(vec) rep(i, vec.size()) {rep(j, vec[i].size()) cout << vec[i][j] << ' '; cout << endl;}; #define printvvv(vec) rep(i, vec.size()) { rep(j, vec[i].size()) { rep(k, vec[i][j].size()) cout << vec[i][j][k] << ' '; cout << " "; }cout << endl; }; #define all1(x) x.begin(),x.end() #define all2(x) x.rbegin(), x.rend() #define so(x) sort(all1(x)) #define re(x) reverse(all1(x)) #define rso(x) sort(all2(x)) #define vco(x, a) count(all1(x), a) #define per(x) next_permutation(all1(x)) #define iINF 2147483647 #define llINF 9223372036854775807 #define INF 4000000000000000000 #define mod 998244353 #define mod2 1000000007 template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;} template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;} vpi pf(int N) { vector<pair<int, int> > res; for (int a = 2; a*a <= N; a++) { if (N%a != 0) continue; int ex = 0; while(N%a == 0) { ex++; N /= a; } res.push_back({a, ex}); } if (N != 1) res.push_back({N, 1}); return res; } vector<long long> fact, fact_inv, inv; void init_nCk(int SIZE, int MOD) { fact.resize(SIZE + 5); fact_inv.resize(SIZE + 5); inv.resize(SIZE + 5); fact[0] = fact[1] = 1; fact_inv[0] = fact_inv[1] = 1; inv[1] = 1; for (int i = 2; i < SIZE + 5; i++) { fact[i] = fact[i - 1] * i % MOD; inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD; fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD; } } long long nCk(int n, int k, int MOD) { // assert(!(n < k)); // assert(!(n < 0 || k < 0)); if((n < k) || (n < 0 || k < 0)) return 0; return fact[n] * (fact_inv[k] * fact_inv[n - k] % MOD) % MOD; } int main() { //アルゴリズム一覧を見る //嘘解法ですか init_nCk(2e7, mod); int q; cin >> q; int sum = 0; while(q--){ int a, b; cin >> a >> b; vpi vec = pf(a); rep(i, vec.size()) sum += vec[i].second; cout << nCk(sum-1, b-1, mod) << endl; } }