結果
問題 | No.2318 Phys Bone Maker |
ユーザー |
![]() |
提出日時 | 2023-05-26 21:32:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,509 ms / 3,000 ms |
コード長 | 1,060 bytes |
コンパイル時間 | 4,059 ms |
コンパイル使用メモリ | 255,992 KB |
最終ジャッジ日時 | 2025-02-13 05:57:56 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001 int main(){ long long n; cin>>n; vector<long long> ys; for(long long i=1;i*i<=n;i++){ if(n%i==0){ ys.push_back(i); if(i*i!=n)ys.push_back(n/i); } } vector<long long> ps; { for(long long i=2;i*i<=n;i++){ if(n%i==0){ ps.push_back(i); while(n%i==0)n /= i; } } if(n!=1)ps.push_back(n); } sort(ys.begin(),ys.end()); vector<mint> dp(ys.size()); dp[0] = 1; rep(i,ys.size()){ for(int j=i+1;j<ys.size();j++){ if(ys[j]%ys[i]==0){ mint v = 1; rep(k,ps.size()){ int x = 0,y = 0; long long t = ys[i]; while(t%ps[k]==0){ x++; t /= ps[k]; } t = ys[j]; while(t%ps[k]==0){ y++; t /= ps[k]; } if(x==y)v *= x+1; } dp[j] += dp[i] * v; } } } cout<<dp.back().val()<<endl; return 0; }