結果
問題 | No.2318 Phys Bone Maker |
ユーザー |
|
提出日時 | 2023-06-09 05:22:39 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 772 ms / 3,000 ms |
コード長 | 2,731 bytes |
コンパイル時間 | 3,908 ms |
コンパイル使用メモリ | 267,440 KB |
実行使用メモリ | 12,220 KB |
最終ジャッジ日時 | 2024-12-31 12:16:17 |
合計ジャッジ時間 | 11,724 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#include <bits/stdc++.h>#pragma GCC optimize("O3")#pragma GCC target("sse4")using namespace std;using ll = long long;static constexpr ll Q = 998244353;template <typename K, typename V>using Map = map<K, V>;template <typename Int>vector<Int> factorize(Int n, Int i=1) {vector<Int> f;f.reserve( sqrt(n) );for (; i*i < n; ++i)if (n % i == 0)f.push_back(i);i -= (i - (n / i) == 1);for (; i >= 1; i--)if (n % i == 0)f.push_back(n/i);return f;}struct sieve {static constexpr size_t N = 1000001;int spf[N] = {};sieve() {spf[0] = spf[1] = -1;for (int i = 3; i <= N; i += 2) spf[i] = i;for (int i = 2; i <= N; i += 2) spf[i] = 2; // avoid lots of % laterfor (int i = 3; i*i <= N; i += 2) {if (spf[i] != i) continue;for (int j = i*i; j <= N; j += i)if (spf[j] == j)spf[j] = i;}}inline bool operator()(int n) { return spf[n] == n; }template <class Int>inline Map<Int, int> factors(Int n) {Map<Int, int> mp;while (n != 1) {int p = spf[n];while (n % p == 0) {++mp[p];n /= p;}}return mp;}} prime;int z{-1};ll primes[78498];signed main() {ll N;cin >> N;unordered_map<ll, ll> dp;dp[1] = 1;auto facts = factorize(N);int X = facts.size();// dp[x] = sum(dp[y]*Z forall y such that x%y==0) where Z is # of z s.t. lcm(y,z) = xfor (int i = 2; i < sieve::N; ++i)if (prime(i))primes[++z] = i;vector<Map<ll,int>> prime_facs(X);for (int i = 0; i < X; ++i) {ll x = facts[i];if (x < sieve::N)prime_facs[i] = prime.factors(x);else {ll y = x;for (int j = 0; j < 78498; ++j) {int p = primes[j];while (y % p == 0) {y /= p;++prime_facs[i][p];}if (y == 1) break;}if (y != 1)prime_facs[i][y] = 1;}}for (int i = 1; i < X; ++i) {ll x = facts[i];auto& pfx = prime_facs[i];for (int j = 0; j < i; ++j) {ll y = facts[j];if (x % y != 0) continue;ll ways = dp[y]; // # of z where lcm(y,z) = xauto& pfy = prime_facs[j];for (auto [p, cnt] : pfx)if (pfy[p] == cnt)ways = ways * (cnt+1) % Q;dp[x] = (dp[x]+ways) % Q;}}cout << dp[N] << '\n';}