結果
| 問題 |
No.2318 Phys Bone Maker
|
| コンテスト | |
| ユーザー |
 7iz6
|
| 提出日時 | 2023-05-26 22:55:36 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,711 bytes |
| コンパイル時間 | 2,138 ms |
| コンパイル使用メモリ | 154,408 KB |
| 最終ジャッジ日時 | 2025-02-13 08:10:09 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 TLE * 1 |
| other | AC * 37 TLE * 8 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <string>
#include <set>
#include <tuple>
#include <bitset>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <limits>
#include <iomanip>
#include <cassert>
#include <sstream>
#include <random>
#include <memory>
// #include <boost/container/flat_set.hpp> // insert: O(log N), erase: O(1)
// using namespace boost::container
// #include <atcoder/all>
// using namespace atcoder;
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define ll long long
#define pii std::pair<int, int>
#define pll std::pair<ll, ll>
#define vi std::vector<int>
#define vii std::vector<std::pair<int, int>>
#define vll std::vector<std::pair<ll, ll>>
#define vvi std::vector<std::vector<int>>
#define vvl std::vector<std::vector<ll>>
#define ALL(v) (v).begin(), (v).end()
#define OUT(v) for(int i = 0, n = (v).size(); i < n; i++) cout << v[i] << " \n"[i+1==n]
// const int MOD = 1e9 + 7;
const int MOD = 998244353;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const double eps = 1e-6;
constexpr double PI = std::acos(-1);
const int di[4] = {0, 1, 0, -1};
const int dj[4] = {1, 0, -1, 0};
const int di8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int dj8[8] = {1, 1, 0, -1, -1, -1, 0, 1};
template<typename T, typename U>
bool operator==(const pair<T, U>& lhs, const pair<T, U>& rhs) {
return (lhs.first == rhs.first && lhs.second == rhs.second);
}
bool is_out(int i, int j, int n) {
return (i < 0 || j < 0 || i >= n || j >= n);
}
bool is_out(int i, int j, int h, int w) {
return (i < 0 || j < 0 || i >= h || j >= w);
}
template <typename T>
bool PN(T x){if(x <= 1)return false;if(x == 2)return true;for(ll i = 2; i * i <= x; i++)if(x % i == 0)return false; return true;}
ll Comb(int n, int i){ll ans=1;if(i>n||i<0)return 0;if(i==0||i==n)return 1;else{for(int j=1;j<=i;++j){ans*=(n+1-j);ans/=j;ans%=MOD;}}return ans;}
template <typename T>T gcd(T a, T b){if (a < b)std::swap(a,b);return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){if(b>a)std::swap(a,b);T g=gcd(a,b);return a/g*b;}
template <typename T> void chmax(T& a, T b) {a=b>a?b:a;}
template <typename T> void chmin(T& a, T b) {a=b<a?b:a;}
// 約数列挙
template<typename T> vector<T> divisor(T n) {
vector<T> res;
for (long long i = 1; i * i <= n; i++) {
if (n % i == 0) {
res.push_back(i);
if (i != n / i) {
res.push_back(n / i);
}
}
}
sort(res.begin(), res.end());
return res;
}
template <class T>
T modpow(T a, T b, T mod) {
// a^b mod m を求める
long long p=1,q=a;
for(int i = 0; i < 30; i++) {
if((b & (1LL << i)) != 0) p*=q, p%=mod;
q*=q; q%=mod;
}
return p;
}
template <class T>
T Div(T a, T b, T m) {
return (a * modpow(b, m - 2, m)) % m;
}
// 区間更新遅延評価セグ木(葉の値を別の値に更新)
// 区間の最大値を返す(RMQ)。
namespace seg_update
{
using S = ll;
using F = ll;
const ll ID = 1e18 + 1;
const int N_SEG = 1e5 + 5;
S op(S l, S r) { return max(l, r); }
S e() { return 0; }
S mapping(F l, S r) { return l; }
F composition(F f, F g) { return (f == ID) ? g : f; }
F id() { return ID; }
// atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(N_SEG);
}
// 区間加算遅延評価セグ木(葉の値を定数倍+定数加算) ai <- ai * a + b;
// 区間の和を返す。
namespace seg_add{
struct S {
ll a;
int size;
};
struct F {
ll a, b;
};
S op(S l, S r) { return S{l.a + r.a, l.size + r.size}; }
S e() { return S{0, 0}; }
S mapping(F l, S r) { return S{r.a * l.a + r.size * l.b, r.size}; }
F composition(F f, F g) { return F{g.a * f.a, g.b * f.a + f.b}; }
F id() { return {1, 0}; }
}
/// @brief 重み付き Union-Find 木
/// @tparam Type 重みの表現に使う型
/// @note 1.1 シンプルな実装
/// @see https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/weighted-union-find
template <class Type>
class WeightedUnionFind
{
public:
WeightedUnionFind() = default;
/// @brief 重み付き Union-Find 木を構築します。
/// @param n 要素数
explicit WeightedUnionFind(size_t n)
: m_parents(n)
, m_sizes(n, 1)
, m_diffWeights(n)
{
std::iota(m_parents.begin(), m_parents.end(), 0);
}
/// @brief 頂点 i の root のインデックスを返します。
/// @param i 調べる頂点のインデックス
/// @return 頂点 i の root のインデックス
int find(int i)
{
if (m_parents[i] == i)
{
return i;
}
const int root = find(m_parents[i]);
m_diffWeights[i] += m_diffWeights[m_parents[i]];
// 経路圧縮
return (m_parents[i] = root);
}
/// @brief a のグループと b のグループを統合します。
/// @param a 一方のインデックス
/// @param b 他方のインデックス
/// @param w (b の重み) - (a の重み)
void merge(int a, int b, Type w)
{
w += weight(a);
w -= weight(b);
a = find(a);
b = find(b);
if (a != b)
{
// union by size (小さいほうが子になる）
if (m_sizes[a] < m_sizes[b])
{
std::swap(a, b);
w = -w;
}
m_sizes[a] += m_sizes[b];
m_parents[b] = a;
m_diffWeights[b] = w;
}
}
/// @brief (b の重み) - (a の重み) を返します。
/// @param a 一方のインデックス
/// @param b 他方のインデックス
/// @remark a と b が同じグループに属さない場合の結果は不定です。
/// @return (b の重み) - (a の重み)
Type diff(int a, int b)
{
return (weight(b) - weight(a));
}
/// @brief a と b が同じグループに属すかを返します。
/// @param a 一方のインデックス
/// @param b 他方のインデックス
/// @return a と b が同じグループに属す場合 true, それ以外の場合は false
bool connected(int a, int b)
{
return (find(a) == find(b));
}
/// @brief i が属するグループの要素数を返します。
/// @param i インデックス
/// @return i が属するグループの要素数
int size(int i)
{
return m_sizes[find(i)];
}
private:
// m_parents[i] は i の 親,
// root の場合は自身が親
std::vector<int> m_parents;
// グループの要素数 (root 用)
// i が root のときのみ, m_sizes[i] はそのグループに属する要素数を表す
std::vector<int> m_sizes;
// 重み
std::vector<Type> m_diffWeights;
Type weight(int i)
{
find(i); // 経路圧縮
return m_diffWeights[i];
}
};
template<typename T>
size_t LIS(const std::vector<T>& v) {
size_t sz = v.size();
std::vector<T> ret;
for(const T& val: v) {
auto it = std::lower_bound(ret.begin(), ret.end(), val);
if(it == ret.end()) {
ret.push_back(val);
} else {
*it = val;
}
}
return ret.size();
}
struct UndirectedGraph {
std::vector<std::vector<pair<int, long long>>> G;
std::vector<int> u, v;
std::vector<long long> w;
int n;
int m;
UndirectedGraph(int _n, int _m) {
n = _n;
m = _m;
u.resize(n);
v.resize(n);
w.resize(n, 1);
G.resize(n + 10);
}
void read_uv() {
for(int i = 0; i < m; i++) {
cin >> u[i] >> v[i];
u[i]--;
v[i]--;
G[u[i]].push_back({v[i], 1});
G[v[i]].push_back({u[i], 1});
}
}
void read_uvw() {
for(int i = 0; i < m; i++) {
cin >> u[i] >> v[i] >> w[i];
u[i]--;
v[i]--;
G[u[i]].push_back({v[i], w[i]});
G[v[i]].push_back({u[i], w[i]});
}
}
// return distance and pre points
std::pair<std::vector<long long>, std::vector<int>> dijkstra(int s) {
typedef std::pair<long long, pair<int,int> > Edge;
std::vector<long long> dist(n, LINF);
std::vector<int> pre(n, -1);
dist[s] = 0;
pre[s] = s;
std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge> > pq;
pq.push(Edge{0, {s, -1}});
while(!pq.empty()) {
Edge e = pq.top(); pq.pop();
int from = e.second.first;
long long cost = e.first;
if(dist[from] < cost) continue;
for(auto[nx, weight]: G[from]) {
if(dist[nx] > dist[from] + weight) {
dist[nx] = dist[from] + weight;
pq.push(Edge{dist[nx], {nx, from}});
pre[nx] = from;
}
}
}
return {dist, pre};
}
};
void solve(){
long long n;
cin >> n;
long long n2 = n;
vector<long long> div = divisor(n);
vector<int> cnt(1000001, 0);
for(long long i = 2; i * i <= n; i++) {
for(long long j = i; j * j <= n; j += i) {
cnt[j]++;
}
}
vector<int> primes;
for(int i = 2; i <= 1000000; i++) {
if(cnt[i] == 1) primes.push_back(i);
}
map<long long, long long> dp;
dp[1] = 1;
vector<pair<long long, int>> v;
for(int p: primes) {
int cnt = 0;
while(n2%p==0) {
cnt++;
n2/=p;
}
if(cnt>0) v.push_back({p, cnt});
}
if(n2 != 0) v.push_back({n2, 1});
vector<long long> muls;
muls.push_back(1);
for(auto p: v) {
int msize = muls.size();
long long val = 1;
for(int i = 0; i < p.second; i++) {
val *= (ll)p.first;
for(int j = 0; j < msize; j++) muls.push_back((ll)muls[j] * val);
}
}
sort(muls.begin(), muls.end());
muls.erase(unique(muls.begin(), muls.end()), muls.end());
for(auto val: muls) cerr << val << " ";
cerr << endl;
cerr << muls.size() << " " << div.size() << endl;
for(long long d: div) {
for(long long mul: muls) {
if(long long l = lcm(d, mul); l > d) {
dp[l] += dp[d];
dp[l] %= MOD;
}
}
}
cout << dp[n] << endl;
}
int main(void){
solve();
return 0;
}