結果
問題 | No.2896 Monotonic Prime Factors |
ユーザー |
![]() |
提出日時 | 2024-09-26 17:55:12 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,212 bytes |
コンパイル時間 | 2,978 ms |
コンパイル使用メモリ | 245,148 KB |
実行使用メモリ | 19,072 KB |
最終ジャッジ日時 | 2024-09-26 17:55:24 |
合計ジャッジ時間 | 7,889 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 16 RE * 2 |
ソースコード
#include<bits/stdc++.h> #define int long long using namespace std; #define fi first #define sc second #define pii pair<int,int> #define pb push_back #define umap unordered_map #define mset multiset #define pq priority_queue #define ull unsigned long long #define i128 __int128 const int maxn=1e6+10; const int mod=998244353; int n,cnt,fr[maxn],ifr[maxn]; int quickpow(int x,int y){ int p=1; for(int i=y;i;i>>=1) p=(p*((i&1)?x:1))%mod,x=(x*x)%mod; return p; } int inv(int x){ return quickpow(x,mod-2); } int C(int x,int y){ if(x<0||y<0||x-y<0) return 0; return fr[x]*ifr[y]%mod*ifr[x-y]%mod; } void solve(){ cin>>n,fr[0]=1; for(int i=1;i<=1e6;i++) fr[i]=(fr[i-1]*i)%mod; ifr[1000000]=inv(fr[1000000]); for(int i=999999;~i;i--) ifr[i]=(ifr[i+1]*(i+1))%mod; while(n--){ int x,y; cin>>x>>y; for(int i=2;i*i<=x;i++){ while(x%i==0) x/=i,cnt++; } cnt+=(x>1); cout<<C(cnt-1,y-1)<<endl; } } signed main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int t=1; // cin>>t; while(t--) solve(); return 0; } /* Samples input: output: THINGS TODO: ??freopen??????? ???? ???????????? */