結果
問題 | No.2798 Multiple Chain |
ユーザー | ir5 |
提出日時 | 2024-06-29 01:47:31 |
言語 | C++23(gcc13) (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 83 ms / 2,000 ms |
コード長 | 6,660 bytes |
コンパイル時間 | 2,339 ms |
コンパイル使用メモリ | 145,152 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-29 01:47:37 |
合計ジャッジ時間 | 4,655 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 24 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 31 ms
5,376 KB |
testcase_06 | AC | 24 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 3 ms
5,376 KB |
testcase_14 | AC | 14 ms
5,376 KB |
testcase_15 | AC | 18 ms
5,376 KB |
testcase_16 | AC | 19 ms
5,376 KB |
testcase_17 | AC | 21 ms
5,376 KB |
testcase_18 | AC | 22 ms
5,376 KB |
testcase_19 | AC | 23 ms
5,376 KB |
testcase_20 | AC | 18 ms
5,376 KB |
testcase_21 | AC | 15 ms
5,376 KB |
testcase_22 | AC | 23 ms
5,376 KB |
testcase_23 | AC | 23 ms
5,376 KB |
testcase_24 | AC | 20 ms
5,376 KB |
testcase_25 | AC | 18 ms
5,376 KB |
testcase_26 | AC | 20 ms
5,376 KB |
testcase_27 | AC | 9 ms
5,376 KB |
testcase_28 | AC | 11 ms
5,376 KB |
testcase_29 | AC | 14 ms
5,376 KB |
testcase_30 | AC | 21 ms
5,376 KB |
testcase_31 | AC | 13 ms
5,376 KB |
testcase_32 | AC | 11 ms
5,376 KB |
testcase_33 | AC | 12 ms
5,376 KB |
testcase_34 | AC | 24 ms
5,376 KB |
testcase_35 | AC | 16 ms
5,376 KB |
testcase_36 | AC | 20 ms
5,376 KB |
testcase_37 | AC | 15 ms
5,376 KB |
testcase_38 | AC | 16 ms
5,376 KB |
testcase_39 | AC | 11 ms
5,376 KB |
testcase_40 | AC | 24 ms
5,376 KB |
testcase_41 | AC | 37 ms
5,376 KB |
testcase_42 | AC | 83 ms
5,376 KB |
testcase_43 | AC | 54 ms
5,376 KB |
testcase_44 | AC | 32 ms
5,376 KB |
testcase_45 | AC | 2 ms
5,376 KB |
testcase_46 | AC | 2 ms
5,376 KB |
testcase_47 | AC | 2 ms
5,376 KB |
testcase_48 | AC | 2 ms
5,376 KB |
testcase_49 | AC | 2 ms
5,376 KB |
testcase_50 | AC | 2 ms
5,376 KB |
testcase_51 | AC | 18 ms
5,376 KB |
testcase_52 | AC | 19 ms
5,376 KB |
testcase_53 | AC | 10 ms
5,376 KB |
ソースコード
#include <algorithm> #include <cassert> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <numeric> #include <vector> #include <map> #include <set> #include <queue> #include <functional> #include <iomanip> using namespace std; using ll = long long; class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n; public:range(int n_):i({0}),n({n_}){}range(int i_,int n_):i({i_}),n({n_}){}I& begin(){return i;}I& end(){return n;}}; template<typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; } template<typename T> ostream& operator<<(ostream& os, const vector<T>& obj) { os << "{"; for (const auto& e : obj) os << e << ", "; return os << "}"; } template<typename T> ostream& operator<<(ostream& os, const set<T>& obj) { os << "set{"; for (const auto& e : obj) os << e << ", "; return os << "}"; } template<typename T, typename U> ostream& operator<<(ostream& os, const map<T, U>& obj) { os << "map{"; for (const auto& e : obj) os << e << ", "; return os << "}"; } template<typename T> void take(vector<T>& vec, int n) { vec.resize(n); for (int i = 0; i < n; ++i) cin >> vec[i]; } template<typename T, size_t X> ostream& operator<<(ostream& os, const array<T, X>& obj) { os << "{"; for (const auto& e : obj) os << e << ", "; return os << "}"; } #ifdef ONLINE_JUDGE #define dump(expr) ; #else #define dump(expr) { cerr << "\033[33m#L" << __LINE__ << ": " << expr << "\033[39m" << endl; } #endif namespace solver { template<typename T1, typename T2> struct In2 { T1 a; T2 b; friend std::istream& operator>>(std::istream& is, In2& obj) { T1 t1; T2 t2; is >> t1 >> t2; obj = {t1, t2}; return is; } }; template<typename T1, typename T2, typename T3> struct In3 { T1 a; T2 b; T3 c; friend std::istream& operator>>(std::istream& is, In3& obj) { T1 t1; T2 t2; T3 t3; is >> t1 >> t2 >> t3; obj = {t1, t2, t3}; return is; } }; ll n; void read() { cin >> n; } using RetType = int; /* map<ll, ll> memo; ll dp(ll n0, ll a0) { if (memo.count(n0)) reutnr memo[n0]; ll res = 1; // n0 = a * a * x // a <= x for (ll a = a0; a * a * a <= n0; a += a1min) if (n0 % (a * a) == 0) { res += dp(n0 / a, a); } // a >= x for (ll x = 1; ) return memo[n0] = res; } */ /* int s; using A = vector<pair<int, int>>; // curr, sum + target * 1000 int sum0; map<A, int> memo; int dfs(A p) { ranges::sort(p); // dump(p); if (memo.count(p)) return memo[p]; // dump(curr << " " << sum); int ss = 0; for (int i : range(s)) ss += p[i].second % 1000; if (ss == sum0) { return 1; } A next(s); auto dfs2 = [&](auto self, int idx, int tot) -> int { if (idx == s) { if (tot) return dfs(next); return 0; } int curr = p[idx].first; int sum = p[idx].second % 1000; int target = p[idx].second / 1000; int res = 0; for (int val : range(curr, 1 + target)) { if (val + sum > target) break; next[idx].first = val; next[idx].second = sum + val + target * 1000; res += self(self, idx + 1, tot + val); } return res; }; int res = dfs2(dfs2, 0, 0); return memo[p] = res; } RetType run() { map<ll, ll> mp; for (ll p = 2; p * p * p <= n; ++p) { while (n % p == 0) mp[p]++, n/= p; } if (n > 1) { ll x = (ll)(sqrt(n) + 0.5); if (x * x == n) mp[x] += 2; else mp[n]++; } ll res = 0; for (int size = 1; size <= 100; ++size) { ll t = 1; // a[1] + ... + a[size] = e // a[i] <= ... <= a[size] for (auto p : mp) { int e = p.second; if (e <= 1) continue; vector<vector<ll>> dp(e + 1, vector<ll>(e + 1)); dp[0][0] = 1; for ([[maybe_unused]] ll iter : range(size)) { vector<vector<ll>> next(e + 1, vector<ll>(e + 1)); for (int now : range(e + 1)) for (int sum : range(e + 1)) { for (int val : range(now, e + 1)) { if (sum + val > e) break; next[val][sum + val] += dp[now][sum]; } } dp.swap(next); if (size == 2) dump(dp); } ll tot = 0; for (int i : range(e + 1)) tot += dp[i][e]; t *= tot; } if (size <= 3) dump(size << " " << t); res += t; } return res; s = (int)mp.size(); vector<int> vm(s); int idx = 0; for (auto p : mp) vm[idx++] = p.second; ranges::sort(vm); while (vm.size() > 0 && vm[0] == 1) vm.erase(vm.begin()); s = (int)vm.size(); sum0 = accumulate(vm.begin(), vm.end(), 0); dump(vm); if (s == 0) { dump("NONE"); return 1; } memo.clear(); A z(s); for (int i : range(s)) z[i].second = vm[i] * 1000; int res = dfs(z); return res; } */ map<ll, ll> memo[61]; map<ll, ll> factors; ll dp(ll len, ll m) { if (len == 0) return 0; if (len == 1) return 1; if (memo[len].count(m)) return memo[len][m]; ll res = 0; for (auto [f, _] : factors) { ll m1 = m; ll e = 0; while (m1 % f == 0 && e < len) m1 /= f, e++; if (e == len) { res += dp(len - 1, m1); } } /* ll m2 = m; for (ll a = 2; a * a * a <= m; ++a) { // if (len >= 4 && a * a * a * a > m) break; ll e = 0; ll m1 = m; while (m1 % a == 0 && e < len) m1 /= a, e++; while (m2 % a == 0) m2 /= a; if (e == len) { if (len <= 2) dump(len << " " << m << " -> " << m1) res += dp(len - 1, m1); } } if (len == 2 && m2 > 1) { ll x = (ll)(sqrt(m2) + 0.5); if (x * x == m2) { assert(m % (x * x) == 0); if (len <= 2) dump(len << " " << m << " -> " << m / (x * x)) res += dp(len - 1, m / (x * x)); } } */ if (len <= 4) dump("memo" << len << " " << m << ": " << res) return memo[len][m] = res; } RetType run() { for (ll a = 1; a * a * a <= n; ++a) { if (n % (a * a) == 0) factors[a]++; if (n % a == 0) { ll b = (ll)sqrt(n / a + 0.5); if (n / a == b * b) factors[b]++; } } dump(factors); /* for (ll a = 1; a <= n; ++a) { dump(a); if (n % (a * a) == 0) { assert(factors.count(a)); } } dump("ST"); */ ll res = dp(60, n); dump(dp(1, n)); dump(dp(2, n)); dump(dp(3, n)); return res; } } // namespace template <typename F> void run(F f) { if constexpr (std::is_same_v<decltype(f()), void>) f(); else cout << f() << endl; } int main(int argc, char** argv) { cerr << fixed << setprecision(12); cout << fixed << setprecision(12); int testcase = 1; if (argc > 1) testcase = atoi(argv[1]); while (testcase--) { solver::read(); } run(solver::run); }