結果
問題 | No.2818 A Game I Play to Pass the Time |
ユーザー | highlighter |
提出日時 | 2024-04-26 20:59:03 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 534 ms / 2,000 ms |
コード長 | 1,055 bytes |
コンパイル時間 | 6,520 ms |
コンパイル使用メモリ | 336,668 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-04-26 21:00:40 |
合計ジャッジ時間 | 23,706 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 534 ms
5,248 KB |
testcase_02 | AC | 490 ms
5,376 KB |
testcase_03 | AC | 491 ms
5,376 KB |
testcase_04 | AC | 513 ms
5,376 KB |
testcase_05 | AC | 485 ms
5,376 KB |
testcase_06 | AC | 480 ms
5,376 KB |
testcase_07 | AC | 482 ms
5,376 KB |
testcase_08 | AC | 467 ms
5,376 KB |
testcase_09 | AC | 478 ms
5,376 KB |
testcase_10 | AC | 478 ms
5,376 KB |
testcase_11 | AC | 391 ms
5,376 KB |
testcase_12 | AC | 237 ms
5,376 KB |
testcase_13 | AC | 314 ms
5,376 KB |
testcase_14 | AC | 409 ms
5,376 KB |
testcase_15 | AC | 376 ms
5,376 KB |
testcase_16 | AC | 423 ms
5,376 KB |
testcase_17 | AC | 349 ms
5,376 KB |
testcase_18 | AC | 356 ms
5,376 KB |
testcase_19 | AC | 433 ms
5,376 KB |
testcase_20 | AC | 412 ms
5,376 KB |
testcase_21 | AC | 466 ms
5,376 KB |
testcase_22 | AC | 311 ms
5,376 KB |
testcase_23 | AC | 289 ms
5,376 KB |
testcase_24 | AC | 294 ms
5,376 KB |
testcase_25 | AC | 279 ms
5,376 KB |
testcase_26 | AC | 438 ms
5,376 KB |
testcase_27 | AC | 427 ms
5,376 KB |
testcase_28 | AC | 367 ms
5,376 KB |
testcase_29 | AC | 376 ms
5,376 KB |
testcase_30 | AC | 378 ms
5,376 KB |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; using mint=modint998244353; int prime[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97}; vector<pair<int,int>> factorize(long long N,int M){ vector<pair<int,int>> vec; for(int i=0;i<M;i++){ int count=0; while(N%prime[i]==0){ N/=prime[i]; count++; } vec.push_back(make_pair(prime[i],count)); } return vec; } int main(){ int M,Q; scanf("%d%d",&M,&Q); mint inv[61]; inv[1]=1; for(int i=2;i<61;i++){ inv[i]=-inv[998244353%i]*mint(998244353/i); } for(;Q--;){ long long N,S; scanf("%lld%lld",&N,&S); vector<pair<int,int>> vec=factorize(N,M); mint ans=1; for(auto p : vec){ vector<mint> data(p.second+1); data[0]=1; for(int i=1;i<=p.second;i++){ data[i]=data[i-1]*mint(p.first); } mint res=data[p.second]; mint mem=1; for(int i=1;i<=p.second;i++){ mem*=inv[i]*mint(S-2+i); res+=data[p.second-i]*mem; } ans*=res; } ans*=mint(S); printf("%d\n",ans.val()); } }