結果
問題 | No.2896 Monotonic Prime Factors |
ユーザー | tottoripaper |
提出日時 | 2024-09-21 02:50:43 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 207 ms / 2,000 ms |
コード長 | 1,776 bytes |
コンパイル時間 | 2,455 ms |
コンパイル使用メモリ | 215,156 KB |
実行使用メモリ | 35,088 KB |
最終ジャッジ日時 | 2024-09-21 02:50:50 |
合計ジャッジ時間 | 6,660 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using ll = std::int64_t;std::tuple<ll, ll, ll> extgcd(ll a, ll b){ll s1 = 1, t1 = 0, s2 = 0, t2 = 1;while(b != 0){std::tie(s1, t1, s2, t2) = std::make_tuple(s2, t2, s1 - (a / b) * s2, t1 - (a / b) * t2);std::tie(a, b) = std::make_tuple(b, a % b);}return std::make_tuple(s1, t1, a);}ll inv(ll a, ll n){ll inv_a;std::tie(inv_a, std::ignore, std::ignore) = extgcd(a, n);inv_a %= n;if(inv_a < 0){inv_a += n;}return inv_a;}int main(){std::cin.tie(nullptr);std::ios::sync_with_stdio(false);const int MAX = 100'000;std::vector<int> primes, spf(MAX + 1, 0);for(int i=2;i<=MAX;i++){if(spf[i] == 0){primes.emplace_back(i);spf[i] = i;}for(auto &p : primes){if(p > spf[i] || i > MAX / p){break;}spf[i * p] = p;}}const int MAX2 = 2'000'000;const int MOD = 998244353;std::vector<ll> fact(MAX2 + 1, 0), invFact(MAX2 + 1, 0);fact[0] = 1;for(int i=1;i<=MAX2;i++){fact[i] = fact[i - 1] * i % MOD;}invFact[MAX2] = inv(fact[MAX2], MOD);for(int i=MAX2;i>=1;i--){invFact[i - 1] = invFact[i] * i % MOD;}int Q;std::cin >> Q;int count = 0;for(int i=0;i<Q;i++){int A, B;std::cin >> A >> B;while(A > 1){int p = spf[A];while(A % p == 0){count += 1;A /= p;}}// (count - 1) choose (B - 1)ll res = 0;if(count - 1 >= B - 1){res = fact[count - 1] * invFact[B - 1] % MOD * invFact[count - B] % MOD;}std::cout << res << std::endl;}}