結果
問題 | No.2318 Phys Bone Maker |
ユーザー |
|
提出日時 | 2023-05-26 23:30:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,955 ms / 3,000 ms |
コード長 | 1,477 bytes |
コンパイル時間 | 5,299 ms |
コンパイル使用メモリ | 270,188 KB |
最終ジャッジ日時 | 2025-02-13 08:37:12 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#include<bits/stdc++.h>using namespace std;#include<atcoder/all>using namespace atcoder;using ll = long long;ll x;vector<long long> divisor(long long n) {vector<long long> ret;for (long long i = 1; i * i <= n; i++) {if (n % i == 0) {ret.push_back(i);if (i * i != n) ret.push_back(n / i);}}sort(ret.begin(), ret.end()); // 昇順に並べるreturn ret;}template <typename T>vector<pair<T, T>> prime_factor(T n) {vector<pair<T, T>> ret;for (T i = 2; i * i <= n; i++) {if (n % i != 0) continue;T tmp = 0;while (n % i == 0) {tmp++;n /= i;}ret.push_back(make_pair(i, tmp));}if (n != 1) ret.push_back(make_pair(n, 1));return ret;}using mit = modint998244353;unordered_map<ll,ll> mp;unordered_map<ll,mit> dp;unordered_map<ll,vector<ll>> divisor_mp;ll cnt_prime(ll n,ll x){int cnt = 0;while(n%x==0){cnt++;n/=x;}return cnt;}void solve(){auto v = divisor(x);for(auto &i:v){divisor_mp[i] = divisor(i);}dp[1] = 1;auto pv = prime_factor(x);for(auto &i:v){for(auto &j:divisor_mp[i]){if(j==i)continue;mit mul = 1;for(auto &[p,x]:pv){if(cnt_prime(i,p)==cnt_prime(j,p)){mul *= cnt_prime(i,p)+1;}}dp[i] += dp[j]*(mul);}}cout<<dp[x].val()<<endl;}signed main(){cin.tie(nullptr);ios::sync_with_stdio(false);cin >> x;solve();}