結果
問題 |
No.3236 累乗数大好きbot
|
ユーザー |
![]() |
提出日時 | 2025-08-15 22:45:52 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 125 ms / 4,000 ms |
コード長 | 9,591 bytes |
コンパイル時間 | 3,179 ms |
コンパイル使用メモリ | 285,712 KB |
実行使用メモリ | 10,328 KB |
最終ジャッジ日時 | 2025-08-15 22:46:45 |
合計ジャッジ時間 | 7,698 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> #include <cassert> using namespace std; using ll = long long int; using u64 = unsigned long long; using pll = pair<ll, ll>; // #include <atcoder/all> // using namespace atcoder; #define REP(i, a, b) for (ll i = (a); i < (b); i++) #define REPrev(i, a, b) for (ll i = (a); i >= (b); i--) #define ALL(coll) (coll).begin(), (coll).end() #define SIZE(v) ((ll)((v).size())) #define REPOUT(i, a, b, exp, sep) REP(i, (a), (b)) cout << (exp) << (i + 1 == (b) ? "" : (sep)); cout << "\n" // @@ !! LIM(unordered_map power) // ---- inserted library file unordered_map.cc /* This code is based on https://codeforces.com/blog/entry/62393 */ /* #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; */ template <typename T, typename Enable = void> struct safe_custom_hash; // For integer types (int, ll, u64, unsigned, ....) template <typename T> struct safe_custom_hash<T, typename enable_if<is_integral<T>::value>::type> { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; // For string template <> struct safe_custom_hash<string, void> { static uint64_t mix(uint64_t x) { x += 0x9e3779b97f4a7c15ULL; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL; x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL; return x ^ (x >> 31); } size_t operator()(const string& s) const { static const uint64_t seed = chrono::steady_clock::now().time_since_epoch().count(); uint64_t h = seed ^ 0x9e3779b97f4a7c15ULL; const unsigned char* p = (const unsigned char*)s.data(); size_t n = s.size(); while (n >= 8) { uint64_t v; memcpy(&v, p, 8); h = mix(h ^ v); p += 8; n -= 8; } uint64_t tail = 0; for (size_t i = 0; i < n; ++i) tail |= uint64_t(p[i]) << (8*i); h = mix(h ^ tail); return (size_t)h; } }; template <typename T_key, typename T_value> using my_umap = unordered_map<T_key, T_value, safe_custom_hash<T_key>>; template <typename T_key> using my_uset = unordered_set<T_key, safe_custom_hash<T_key>>; template <typename T_key> using my_umultiset = unordered_multiset<T_key, safe_custom_hash<T_key>>; // ---- end unordered_map.cc // ---- inserted library file algOp.cc // Common definitions // zero, one, inverse template<typename T> const T zero(const T& t) { if constexpr (is_integral_v<T> || is_floating_point_v<T>) { return (T)0; } else { return t.zero(); } } template<typename T> const T one(const T& t) { if constexpr (is_integral_v<T> || is_floating_point_v<T>) { return (T)1; } else { return t.one(); } } template<typename T> const T inverse(const T& t) { if constexpr (is_floating_point_v<T>) { return 1.0 / t; } else { return t.inverse(); } } #ifdef BOOST_MP_CPP_INT_HPP template<> const cpp_int zero(const cpp_int& t) { return cpp_int(0); } template<> const cpp_int one(const cpp_int& t) { return cpp_int(1); } #endif // BOOST_MP_CPP_INT_HPP // begin -- detection ideom // cf. https://blog.tartanllama.xyz/detection-idiom/ namespace tartan_detail { template <template <class...> class Trait, class Enabler, class... Args> struct is_detected : false_type{}; template <template <class...> class Trait, class... Args> struct is_detected<Trait, void_t<Trait<Args...>>, Args...> : true_type{}; } template <template <class...> class Trait, class... Args> using is_detected = typename tartan_detail::is_detected<Trait, void, Args...>::type; // end -- detection ideom template<typename T> // using subst_add_t = decltype(T::subst_add(declval<typename T::value_type &>(), declval<typename T::value_type>())); using subst_add_t = decltype(T::subst_add); template<typename T> using has_subst_add = is_detected<subst_add_t, T>; template<typename T> using add_t = decltype(T::add); template<typename T> using has_add = is_detected<add_t, T>; template<typename T> using subst_mult_t = decltype(T::subst_mult); template<typename T> using has_subst_mult = is_detected<subst_mult_t, T>; template<typename T> using mult_t = decltype(T::mult); template<typename T> using has_mult = is_detected<mult_t, T>; template<typename T> using subst_subt_t = decltype(T::subst_subt); template<typename T> using has_subst_subt = is_detected<subst_subt_t, T>; template<typename T> using subt_t = decltype(T::subt); template<typename T> using has_subt = is_detected<subt_t, T>; template <typename Opdef> struct MyAlg { using T = typename Opdef::value_type; using value_type = T; T v; MyAlg() {} MyAlg(const T& v_) : v(v_) {} MyAlg(T&& v_) : v(move(v_)) {} bool operator==(MyAlg o) const { return v == o.v; } bool operator!=(MyAlg o) const { return v != o.v; } operator T() const { return v; } MyAlg zero() const { return MyAlg(Opdef::zero(v)); } MyAlg one() const { return MyAlg(Opdef::one(v)); } MyAlg inverse() const { return MyAlg(Opdef::inverse(v)); } MyAlg operator/=(const MyAlg& o) { return *this *= o.inverse(); } MyAlg operator/(const MyAlg& o) const { return (*this) * o.inverse(); } MyAlg operator-() const { return zero() - *this; } MyAlg& operator +=(const MyAlg& o) { if constexpr (has_subst_add<Opdef>::value) { Opdef::subst_add(v, o.v); return *this; }else if constexpr (has_add<Opdef>::value) { v = Opdef::add(v, o.v); return *this; }else static_assert("either subst_add or add is needed."); } MyAlg operator +(const MyAlg& o) const { if constexpr (has_add<Opdef>::value) { return MyAlg(Opdef::add(v, o.v)); }else if constexpr (has_subst_add<Opdef>::value) { MyAlg ret(v); Opdef::subst_add(ret.v, o.v); return ret; }else static_assert("either subst_add or add is needed."); } MyAlg& operator *=(const MyAlg& o) { if constexpr (has_subst_mult<Opdef>::value) { Opdef::subst_mult(v, o.v); return *this; }else if constexpr (has_mult<Opdef>::value) { v = Opdef::mult(v, o.v); return *this; }else static_assert("either subst_mult or mult is needed."); } MyAlg operator *(const MyAlg& o) const { if constexpr (has_mult<Opdef>::value) { return MyAlg(Opdef::mult(v, o.v)); }else if constexpr (has_subst_mult<Opdef>::value) { MyAlg ret(v); Opdef::subst_mult(ret.v, o.v); return ret; }else static_assert("either subst_mult or mult is needed."); } MyAlg& operator -=(const MyAlg& o) { if constexpr (has_subst_subt<Opdef>::value) { Opdef::subst_subt(v, o.v); return *this; }else if constexpr (has_subt<Opdef>::value) { v = Opdef::subt(v, o.v); return *this; }else static_assert("either subst_subt or subt is needed."); } MyAlg operator -(const MyAlg& o) const { if constexpr (has_subt<Opdef>::value) { return MyAlg(Opdef::subt(v, o.v)); }else if constexpr (has_subst_subt<Opdef>::value) { MyAlg ret(v); Opdef::subst_subt(ret.v, o.v); return ret; }else static_assert("either subst_subt or subt is needed."); } friend istream& operator >>(istream& is, MyAlg& t) { is >> t.v; return is; } friend ostream& operator <<(ostream& os, const MyAlg& t) { os << t.v; return os; } }; // ---- end algOp.cc // ---- inserted library file power.cc template<typename T> T power(const T& a, ll b) { auto two_pow = a; auto ret = one<T>(a); while (b > 0) { if (b & 1LL) ret *= two_pow; two_pow *= two_pow; b >>= 1; } return ret; } // a >= 0, b >= 0; If overflow, returns -1. ll llpower(ll a, ll b) { if (b == 0) return 1; // 0^0 == 1 if (b == 1) return a; if (a == 0) return 0; if (a == 1) return 1; if (a == 2) { if (b >= 63) return -1; else return 1LL << b; } if (b == 2) { ll ret; if (__builtin_smulll_overflow(a, a, &ret)) return -1; return ret; } ll two_pow = a; ll ret = 1; assert(b > 0); while (true) { if (b & 1LL) { if (__builtin_smulll_overflow(ret, two_pow, &ret)) return -1; } b >>= 1; if (b == 0) break; if (__builtin_smulll_overflow(two_pow, two_pow, &two_pow)) return -1; } return ret; } // a >= 0; Returns x s.t. x*x <= a < (x+1)*(x+1) ll llsqrt(ll a) { ll x = llround(sqrt((double)a)); ll y; if (__builtin_smulll_overflow(x, x, &y) or a < y) return x - 1; else return x; } // a >= 0, m >= 2; Returns x s.t. x^m <= a < (x + 1)^m ll llroot(ll a, ll m) { ll x = llround(pow(a, 1.0 / m)); ll y = llpower(x, m); if (y == -1 or a < y) return x - 1; else return x; } // base >= 2, a >= 1; Returns x s.t. base^{x} <= a < base^{x + 1} ll lllog(ll base, ll a) { ll x = llround(log(a) / log(base)); ll y = llpower(base, x); if (y == -1 or a < y) return x - 1; else return x; } // ---- end power.cc // @@ !! LIM -- end mark -- int main(/* int argc, char *argv[] */) { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << setprecision(20); ll Q; cin >> Q; vector<ll> vec(Q); my_umap<ll, ll> mp; REP(i, 0, Q) { ll n; cin >> n; mp[n] = 1; vec[i] = n; } REP(k, 2, 60) { ll e = llround(floor(pow(10.0, 12.0 / k))); for (ll i = 2; i <= e; i++) { ll x = power<ll>(i, k); auto it = mp.find(x); if (it != mp.end()) it->second = k; } } REP(i, 0, Q) { cout << mp[vec[i]] << "\n"; } return 0; }