結果
問題 | No.2896 Monotonic Prime Factors |
ユーザー | ルク |
提出日時 | 2024-09-20 21:43:16 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 3,805 bytes |
コンパイル時間 | 4,517 ms |
コンパイル使用メモリ | 184,320 KB |
実行使用メモリ | 22,368 KB |
最終ジャッジ日時 | 2024-09-20 21:43:29 |
合計ジャッジ時間 | 11,767 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 44 ms
22,040 KB |
testcase_01 | AC | 41 ms
15,048 KB |
testcase_02 | AC | 43 ms
15,040 KB |
testcase_03 | AC | 42 ms
14,900 KB |
testcase_04 | AC | 1,920 ms
15,104 KB |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | TLE | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #if __has_include(<atcoder/all>) #include <atcoder/all> using namespace atcoder; #endif #include <chrono> #include <unistd.h> using namespace std; using namespace chrono; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i <= (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; using mint = modint998244353; using MINT = modint1000000007; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; constexpr double pi = 3.141592653589793; constexpr ll smallMOD = 998244353; constexpr ll bigMOD = 1000000007; constexpr ll dx[] = {1, 0, -1, 0, 1, -1, -1, 1}; constexpr ll dy[] = {0, 1, 0, -1, 1, 1, -1, -1}; struct Init { Init() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(15); } } init; template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; rep(i, vec.size()) { os << vec[i]; if (i != vec.size() - 1) os << ", "; } os << "]"; return os; } template <typename T> ostream &operator<<(ostream &os, const vector<vector<T>> &vec) { os << "["; rep(i, vec.size()) { os << vec[i]; if (i != vec.size() - 1) os << ", "; } os << "]"; return os; } template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &pair_var) { os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; } template <typename T> ostream &operator<<(ostream &os, const set<T> &st) { os << "{"; for (auto itr = st.begin(); itr != st.end(); ++itr) { os << *itr; if (next(itr) != st.end()) os << ", "; } os << "}"; return os; } void prime_factorize(ll N, vector<pair<ll, ll>> &res) { for (ll p = 2; p * p <= N; ++p) { if (N % p != 0) continue; ll e = 0; while (N % p == 0) { ++e; N /= p; } res.emplace_back(p, e); } if (N != 1) { res.emplace_back(N, 1); } } struct NCR { ll max = 500020, mod = 0; vector<ll> fact, inv, inv_fact; NCR(ll mod = 998244353) { this->mod = mod; fact.resize(max); inv.resize(max); inv_fact.resize(max); fact[0] = 1; fact[1] = 1; inv[0] = 1; inv[1] = 1; inv_fact[0] = 1; inv_fact[1] = 1; for (ll i = 2; i < max; i++) { fact[i] = fact[i - 1] * i % mod; inv[i] = mod - inv[mod % i] * (mod / i) % mod; inv_fact[i] = inv_fact[i - 1] * inv[i] % mod; } } ll nCr(ll n, ll r) { if (n < r) return 0; if (n < 0 || r < 0) return 0; ll x = fact[n]; ll y = inv_fact[n - r]; ll z = inv_fact[r]; return x * ((y * z) % mod) % mod; } }; NCR ncr; void f(ll b, map<ll, ll> &x) { ll sm = 0; for (auto p : x) { sm += p.second; } if (b == 1) { cout << 1 << endl; } else { cout << ncr.nCr(sm - 1, b - 1) << endl; } } int main() { ll n; cin >> n; map<ll, ll> x; rep(i, n) { ll a, b; cin >> a >> b; vector<pair<ll, ll>> res; prime_factorize(a, res); for (auto p : res) { x[p.first] += p.second; } f(b, x); } return 0; }