結果
問題 | No.2318 Phys Bone Maker |
ユーザー |
|
提出日時 | 2023-05-27 04:59:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 361 ms / 3,000 ms |
コード長 | 1,588 bytes |
コンパイル時間 | 985 ms |
コンパイル使用メモリ | 84,916 KB |
最終ジャッジ日時 | 2025-02-13 09:01:11 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>using namespace std;using ll=long long;#define rep(i,n) for(int i=0;i<n;i++)#define rrep(i,n) for(int i=(n)-1;i>=0;i--)#define all(v) v.begin(),v.end()#define rall(v) v.rbegin(),v.rend()template<class T> bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;}template<class T> bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;}const ll MOD=998244353;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);ll N;cin>>N;ll x=1;vector<ll>C;while(x*x<=N){if(N%x==0){C.push_back(x);if(x*x<N)C.push_back(N/x);}x++;}sort(all(C));int l=C.size();vector<ll>P;for(int i=1;i<l;i++){bool flag=true;for(auto p:P){if(C[i]%p==0){flag=false;break;}}if(flag)P.push_back(C[i]);}int m=P.size();vector V(l,vector<int>(m));rep(i,l){rep(j,m){ll p=P[j],q=p;while(C[i]%q==0){q*=p;V[i][j]++;}}}vector<ll>dp(l);dp[0]=1;rep(i,l-1){for(int j=i+1;j<l;j++){if(C[j]%C[i]!=0)continue;ll t=1;rep(k,m){if(V[i][k]==V[j][k]){t*=V[i][k]+1;t%=MOD;}}dp[j]+=t*dp[i];dp[j]%=MOD;}}cout<<dp[l-1]<<"\n";}