結果
問題 |
No.2896 Monotonic Prime Factors
|
ユーザー |
![]() |
提出日時 | 2025-04-04 21:05:19 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 215 ms / 2,000 ms |
コード長 | 2,322 bytes |
コンパイル時間 | 3,452 ms |
コンパイル使用メモリ | 179,368 KB |
実行使用メモリ | 24,668 KB |
最終ジャッジ日時 | 2025-04-04 21:05:29 |
合計ジャッジ時間 | 8,624 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <atcoder/all> using namespace std; using namespace atcoder; using ll = long long; using mint = modint998244353; using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>; using vmi = vector<mint>; using vvmi = vector<vmi>; using vvvmi = vector<vvmi>; #define all(a) (a).begin(), (a).end() #define rep2(i, m, n) for (int i = (m); i < (n); ++i) #define rep(i, n) rep2(i, 0, n) #define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i) #define drep(i, n) drep2(i, n, 0) class Primes{ private: int size_p; vector<bool> is_p; vector<int> primes; vector<int> mobius; void eratos(int n){ for(int i=2; i<=n; i++){ if(minfactor[i] < i)continue; primes.emplace_back(i); mobius[i] = -1; is_p[i] =true; for(int j = 2*i; j<=n; j+=i){ minfactor[j] = min(i, minfactor[j]); mobius[j] = ((j/i) % i == 0) ? 0 : -mobius[j]; } } } public: vector<int> minfactor; Primes(int n){ size_p = n; rep(i, size_p+1)is_p.emplace_back(false); rep(i, size_p+1)minfactor.emplace_back(i); rep(i, size_p+1)mobius.push_back(1); mobius[1] = 1; eratos(size_p); } bool isprime(int n){ return is_p[n]; } vector<int> listPrimes(){ return primes; } int getMobius(int n){return mobius[n];} }; int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); int q; cin >> q; Primes p = Primes(200000); vmi kaijo(5000000); kaijo[0] = kaijo[1] = mint(1); rep2(i, 2, 5000000)kaijo[i] = kaijo[i-1]*mint(i); ll cnt = 0; while(q--){ int a, b; cin >> a >> b; while(a > 1){ cnt++; a /= p.minfactor[a]; } b--; if(cnt-1 < b){ cout << 0 << endl; }else{ mint ans = kaijo[cnt-1]/(kaijo[b]*kaijo[cnt-1-b]); cout << ans.val() << endl; } } return 0; }