結果
問題 |
No.1973 Divisor Sequence
|
ユーザー |
|
提出日時 | 2024-11-15 17:08:47 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 245 ms / 2,000 ms |
コード長 | 1,092 bytes |
コンパイル時間 | 5,916 ms |
コンパイル使用メモリ | 314,236 KB |
実行使用メモリ | 101,004 KB |
最終ジャッジ日時 | 2024-11-15 17:08:57 |
合計ジャッジ時間 | 8,246 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> #if __has_include(<atcoder/all>) #include <atcoder/all> using namespace atcoder; #endif #define rep(i, n) for (int i = 0; i < (n); ++i) using namespace std; using ll = long long; using P = pair<ll, int>; using mint = modint1000000007; vector<P> factorize(ll n) { vector<P> res; for (ll i = 2; i*i <= n; ++i) { if (n%i != 0) continue; res.emplace_back(i, 0); while (n%i == 0) { n /= i; res.back().second++; } } if (n != 1) res.emplace_back(n, 1); return res; } int main() { int n; ll m; cin >> n >> m; auto fs = factorize(m); mint ans = 1; for (auto [p, e] : fs) { vector dp(n, vector<mint>(e+1)); rep(i, e+1) dp[0][i] = 1; rep(i, n-1) { mint sum; for (int k = e; k >= 0; --k) { sum += dp[i][e-k]; dp[i+1][k] = sum; } } mint now; rep(i, e+1) now += dp[n-1][i]; ans *= now; } cout << ans.val() << '\n'; return 0; }