結果
問題 | No.2318 Phys Bone Maker |
ユーザー |
|
提出日時 | 2023-05-26 22:04:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 358 ms / 3,000 ms |
コード長 | 926 bytes |
コンパイル時間 | 2,030 ms |
コンパイル使用メモリ | 176,568 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-25 07:04:10 |
合計ジャッジ時間 | 6,514 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#include<bits/stdc++.h> using namespace std; const int mod=998244353; long long n; int main(){ scanf("%lld",&n); vector<long long>w; for (long long i=1;1ll*i*i<=n;i++) if (n%i==0){ w.push_back(i); if (1ll*i*i!=n) w.push_back(n/i); } vector<long long>q; for (int i=2;1ll*i*i<=n;i++) if (n%i==0){ q.push_back(i); while (n%i==0){ n/=i; } } if (n>1){ q.push_back(n); } sort(w.begin(),w.end()); vector<vector<int>>s((int)w.size(),vector<int>((int)q.size(),0)); for (int i=0;i<w.size();i++){ long long t=w[i]; for (int j=0;j<q.size();j++){ while (t%q[j]==0){ t/=q[j]; s[i][j]++; } } } vector<int>dp((int)w.size(),0); dp[0]=1; for (int i=1;i<w.size();i++) for (int j=0;j<i;j++) if (w[i]%w[j]==0) { long long t=1; for (int k=0;k<q.size();k++) if (s[i][k]==s[j][k]) t=1ll*t*(s[i][k]+1)%mod; dp[i]=(dp[i]+1ll*t*dp[j]%mod)%mod; } printf("%d\n",dp[(int)dp.size()-1]); }