結果

問題 No.2318 Phys Bone Maker
ユーザー hliuser1hliuser1
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 % later
for (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) = x
for (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) = x
auto& 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';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0