結果
問題 | No.2318 Phys Bone Maker |
ユーザー |
![]() |
提出日時 | 2023-05-26 21:47:12 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,363 ms / 3,000 ms |
コード長 | 1,319 bytes |
コンパイル時間 | 3,761 ms |
コンパイル使用メモリ | 258,536 KB |
最終ジャッジ日時 | 2025-02-13 06:21:37 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; typedef modint998244353 mint; typedef long long ll; // makediv vector<ll> makediv(ll n){ vector<ll> ld, ud; for (ll i=1; i*i<=n; i++){ if (n%i == 0){ ld.push_back(i); if (i != n/i){ ud.push_back(n/i); } } } reverse(ud.begin(), ud.end()); ld.insert(ld.end(), ud.begin(), ud.end()); return ld; } // ----- vector<pair<ll,int>> pfact(ll n){ vector<pair<ll,int>> ret; for (ll i=2; i*i<=n; i++){ if (n%i == 0){ int cnt = 0; while (n%i == 0){ n /= i; cnt++; } ret.push_back(pair(i, cnt)); } } if (n > 1) ret.push_back(pair(n, 1)); return ret; } int main(){ ll n; cin >> n; vector<pair<ll,int>> pf = pfact(n); vector<ll> g = makediv(n); int m = g.size(); vector<mint> dp(m); dp[0] = 1; for (int i=0; i<m; i++){ for (int j=0; j<i; j++){ if (g[i] % g[j] == 0){ mint val = 1; for (auto [p,c]: pf){ int cnt_i = 0, cnt_j = 0; { ll k = g[i]; while (k % p == 0){ k /= p; cnt_i++; } } { ll k = g[j]; while (k % p == 0){ k /= p; cnt_j++; } } if (cnt_i == cnt_j){ val *= cnt_i + 1; } } dp[i] += dp[j] * val; } } } cout << dp[m-1].val() << endl; }