Submit Info #53939

Problem Lang User Status Time Memory
Tetration Mod cpp anqooqie AC 36 ms 0.72 MiB

ケース詳細
Name Status Time Memory
2_3_32_00 AC 1 ms 0.61 MiB
example_00 AC 1 ms 0.61 MiB
example_01 AC 1 ms 0.71 MiB
max_00 AC 34 ms 0.70 MiB
max_01 AC 34 ms 0.71 MiB
max_02 AC 34 ms 0.71 MiB
max_1000000000_00 AC 36 ms 0.71 MiB
max_1000000000_01 AC 34 ms 0.70 MiB
max_1000000000_02 AC 34 ms 0.71 MiB
max_998244353_00 AC 16 ms 0.71 MiB
max_998244353_01 AC 18 ms 0.71 MiB
max_998244353_02 AC 16 ms 0.72 MiB
random_00 AC 24 ms 0.71 MiB
random_01 AC 7 ms 0.70 MiB
random_02 AC 4 ms 0.71 MiB
random_03 AC 7 ms 0.71 MiB
random_04 AC 18 ms 0.71 MiB
small_00 AC 1 ms 0.71 MiB

#line 1 "main.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/tetration_mod" #include <cstdint> #include <iostream> #line 1 "/home/anqooqie/.proconlib/tools/tetration_mod.hpp" #line 5 "/home/anqooqie/.proconlib/tools/tetration_mod.hpp" #include <limits> #include <vector> #include <utility> #line 1 "/home/anqooqie/.proconlib/tools/pow.hpp" #include <cstddef> #line 1 "/home/anqooqie/.proconlib/tools/monoid.hpp" #include <algorithm> #line 6 "/home/anqooqie/.proconlib/tools/monoid.hpp" #include <numeric> namespace tools { namespace monoid { template <typename Type, Type E = ::std::numeric_limits<Type>::min()> struct max { using T = Type; static T op(const T lhs, const T rhs) { return ::std::max(lhs, rhs); } static T e() { return E; } }; template <typename Type, Type E = ::std::numeric_limits<Type>::max()> struct min { using T = Type; static T op(const T lhs, const T rhs) { return ::std::min(lhs, rhs); } static T e() { return E; } }; template <typename Type> struct multiplies { using T = Type; static T op(const T lhs, const T rhs) { return lhs * rhs; } static T e() { return T(1); } }; template <typename Type> struct gcd { using T = Type; static T op(const T lhs, const T rhs) { return ::std::gcd(lhs, rhs); } static T e() { return T(0); } }; template <typename Type, Type E> struct update { using T = Type; static T op(const T lhs, const T rhs) { return lhs == E ? rhs : lhs; } static T e() { return E; } }; } } #line 1 "/home/anqooqie/.proconlib/tools/square.hpp" #line 5 "/home/anqooqie/.proconlib/tools/square.hpp" namespace tools { template <typename M> typename M::T square(const typename M::T& x) { return M::op(x, x); } template <typename T> T square(const T& x) { return ::tools::square<::tools::monoid::multiplies<T>>(x); } } #line 7 "/home/anqooqie/.proconlib/tools/pow.hpp" namespace tools { template <typename M> typename M::T pow(const typename M::T& base, const ::std::size_t& exponent) { return exponent == 0 ? M::e() : exponent % 2 == 0 ? ::tools::square<M>(::tools::pow<M>(base, exponent / 2)) : M::op(::tools::pow<M>(base, exponent - 1), base); } template <typename T> T pow(const T& base, const ::std::size_t& exponent) { return ::tools::pow<::tools::monoid::multiplies<T>>(base, exponent); } } #line 1 "/home/anqooqie/.proconlib/tools/prime_factorization.hpp" #include <map> #include <cassert> #include <random> #include <queue> #line 9 "/home/anqooqie/.proconlib/tools/prime_factorization.hpp" #include <cmath> #line 1 "/home/anqooqie/.proconlib/tools/is_prime.hpp" #line 5 "/home/anqooqie/.proconlib/tools/is_prime.hpp" #include <array> #line 1 "/home/anqooqie/.proconlib/tools/prod_mod.hpp" namespace tools { template <typename T1, typename T2, typename T3> constexpr T3 prod_mod(const T1 x, const T2 y, const T3 m) { using u128 = unsigned __int128; u128 prod_mod = u128(x >= 0 ? x : -x) * u128(y >= 0 ? y : -y) % u128(m); if (((x >= 0) ^ (y >= 0)) == 1) prod_mod = u128(m) - prod_mod; return prod_mod; } } #line 1 "/home/anqooqie/.proconlib/tools/pow_mod.hpp" #line 1 "/home/anqooqie/.proconlib/tools/mod.hpp" #include <type_traits> #line 1 "/home/anqooqie/.proconlib/tools/quo.hpp" #line 5 "/home/anqooqie/.proconlib/tools/quo.hpp" namespace tools { template <typename M, typename N> constexpr ::std::common_type_t<M, N> quo(const M lhs, const N rhs) { if (lhs >= 0) { return lhs / rhs; } else { if (rhs >= 0) { return -((-lhs - 1 + rhs) / rhs); } else { return (-lhs - 1 + -rhs) / -rhs; } } } } #line 6 "/home/anqooqie/.proconlib/tools/mod.hpp" namespace tools { template <typename M, typename N> constexpr ::std::common_type_t<M, N> mod(const M lhs, const N rhs) { if constexpr (::std::is_unsigned_v<M> && ::std::is_unsigned_v<N>) { return lhs % rhs; } else { return lhs - ::tools::quo(lhs, rhs) * rhs; } } } #line 6 "/home/anqooqie/.proconlib/tools/pow_mod.hpp" namespace tools { template <typename T1, typename T2, typename T3> constexpr T3 pow_mod(const T1 x, T2 n, const T3 m) { if (m == 1) return 0; T3 r = 1; T3 y = ::tools::mod(x, m); while (n > 0) { if ((n & 1) > 0) { r = ::tools::prod_mod(r, y, m); } y = ::tools::prod_mod(y, y, m); n /= 2; } return r; } } #line 8 "/home/anqooqie/.proconlib/tools/is_prime.hpp" namespace tools { constexpr bool is_prime(const ::std::uint_fast64_t n) { constexpr ::std::array<::std::uint_fast64_t, 7> bases = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; if (n <= 1) return false; if (n == 2) return true; if (n % 2 == 0) return false; ::std::uint_fast64_t d = n - 1; for (; d % 2 == 0; d /= 2); for (const ::std::uint_fast64_t a : bases) { if (a % n == 0) return true; ::std::uint_fast64_t power = d; ::std::uint_fast64_t target = ::tools::pow_mod(a, power, n); bool is_composite = true; if (target == 1) is_composite = false; for (; is_composite && power != n - 1; power *= 2, target = ::tools::prod_mod(target, target, n)) { if (target == n - 1) is_composite = false; } if (is_composite) { return false; } } return true; } } #line 12 "/home/anqooqie/.proconlib/tools/prime_factorization.hpp" namespace tools { template <typename T> ::std::map<T, T> prime_factorization(T n) { assert(1 <= n && n <= 1000000000000000000); ::std::map<T, T> result; for (; n % 2 == 0; n /= 2) { ++result[2]; } if (n == 1) return result; ::std::minstd_rand engine; ::std::queue<T> factors({n}); while (!factors.empty()) { const T factor = factors.front(); factors.pop(); if (::tools::is_prime(factor)) { ++result[factor]; } else { ::std::uniform_int_distribution<T> dist(1, factor - 2); while (true) { T c = dist(engine); if (c == factor - 2) c = factor - 1; T x = 2; T y = 2; T d = 1; while (d == 1) { x = ::tools::prod_mod(x, x, factor); x += c; if (x >= factor) x -= factor; y = ::tools::prod_mod(y, y, factor); y += c; if (y >= factor) y -= factor; y = ::tools::prod_mod(y, y, factor); y += c; if (y >= factor) y -= factor; d = ::std::gcd(::std::abs(x - y), factor); } if (d < factor) { factors.push(d); factors.push(factor / d); break; } } } } return result; } } #line 1 "/home/anqooqie/.proconlib/tools/totient.hpp" #line 7 "/home/anqooqie/.proconlib/tools/totient.hpp" namespace tools { template <typename T> T totient(const T& x) { assert(1 <= x && x <= 1000000000000000000); T prod = 1; for (const auto& [distinct_prime_factor, exponent] : ::tools::prime_factorization(x)) { prod *= ::tools::pow(distinct_prime_factor, exponent - 1) * (distinct_prime_factor - 1); } return prod; } } #line 1 "/home/anqooqie/.proconlib/tools/garner.hpp" #include <optional> #line 7 "/home/anqooqie/.proconlib/tools/garner.hpp" #include <iterator> #line 1 "/home/anqooqie/.proconlib/tools/inv_mod.hpp" #line 1 "/home/anqooqie/.proconlib/tools/extgcd.hpp" #include <tuple> #line 6 "/home/anqooqie/.proconlib/tools/extgcd.hpp" namespace tools { template <typename T> ::std::tuple<T, T, T> extgcd(T prev_r, T r) { T prev_s = 1; T prev_t = 0; T s = 0; T t = 1; while (r != 0) { const T q = ::tools::quo(prev_r, r); const T next_r = prev_r - q * r; prev_r = r; r = next_r; const T next_s = prev_s - q * s; prev_s = s; s = next_s; const T next_t = prev_t - q * t; prev_t = t; t = next_t; } if (prev_r < T(0)) prev_r = -prev_r; return {prev_s, prev_t, prev_r}; } } #line 7 "/home/anqooqie/.proconlib/tools/inv_mod.hpp" namespace tools { template <typename T1, typename T2> constexpr T2 inv_mod(const T1 x, const T2 m) { const auto [x0, y0, gcd] = ::tools::extgcd(x, m); assert(gcd == 1); return ::tools::mod(x0, m); } } #line 13 "/home/anqooqie/.proconlib/tools/garner.hpp" // Source: https://qiita.com/drken/items/ae02240cd1f8edfc86fd // License: unknown // Author: drken namespace tools { template <typename Iterator, typename ModType> ::std::optional<::std::pair<::std::int_fast64_t, ::std::int_fast64_t>> garner(const Iterator& begin, const Iterator& end, const ModType& mod) { ::std::vector<::std::int_fast64_t> b, m; for (auto it = begin; it != end; ++it) { b.push_back(::tools::mod(it->first, it->second)); m.push_back(it->second); } ::std::int_fast64_t lcm = 1; for (::std::size_t i = 0; i < b.size(); ++i) { for (::std::size_t j = 0; j < i; ++j) { ::std::int_fast64_t g = ::std::gcd(m[i], m[j]); if ((b[i] - b[j]) % g != 0) return ::std::nullopt; m[i] /= g; m[j] /= g; ::std::int_fast64_t gi = ::std::gcd(m[i], g), gj = g / gi; do { g = ::std::gcd(gi, gj); gi *= g, gj /= g; } while (g != 1); m[i] *= gi, m[j] *= gj; b[i] %= m[i], b[j] %= m[j]; } } for (::std::size_t i = 0; i < b.size(); ++i) { (lcm *= m[i]) %= mod; } m.push_back(mod); ::std::vector<::std::int_fast64_t> coeffs(m.size(), 1); ::std::vector<::std::int_fast64_t> constants(m.size(), 0); for (::std::size_t k = 0; k < b.size(); ++k) { ::std::int_fast64_t t = ::tools::mod((b[k] - constants[k]) * ::tools::inv_mod(coeffs[k], m[k]), m[k]); for (::std::size_t i = k + 1; i < m.size(); ++i) { (constants[i] += t * coeffs[i]) %= m[i]; (coeffs[i] *= m[k]) %= m[i]; } } return ::std::make_optional<::std::pair<::std::int_fast64_t, ::std::int_fast64_t>>(constants.back(), lcm); } template <typename M, typename Iterator> ::std::optional<::std::pair<M, M>> garner(const Iterator& begin, const Iterator& end) { const auto result = ::tools::garner(begin, end, M::mod()); if (!result) return ::std::nullopt; return ::std::make_optional<::std::pair<M, M>>(M::raw(result->first), M::raw(result->second)); } } #line 13 "/home/anqooqie/.proconlib/tools/tetration_mod.hpp" namespace tools { template <typename T> T tetration_mod(const T a, const T b, const T m) { assert(a >= 0); assert(b >= 0); assert(m >= 1); if (m == 1) return 0; // It returns min(fa^^fb, 2^63 - 1). const auto f = [](const ::std::int_fast64_t fa, const ::std::int_fast64_t fb) { if (fa == 0) return 1 - fb % 2; if (fa == 1) return ::std::int_fast64_t(1); if (fb == 0) return ::std::int_fast64_t(1); if (fb == 1) return fa; if (fb == 2 && fa <= 15) return ::tools::pow(fa, fa); if (fb == 3 && fa <= 3) return ::tools::pow(fa, ::tools::pow(fa, fa)); if (fb == 4 && fa <= 2) return ::tools::pow(fa, ::tools::pow(fa, ::tools::pow(fa, fa))); // Too large return ::std::numeric_limits<::std::int_fast64_t>::max(); }; if (f(a, b) < ::std::numeric_limits<::std::int_fast64_t>::max()) { return f(a, b) % m; } ::std::vector<::std::pair<T, T>> answers; for (const auto& [p, q] : ::tools::prime_factorization(m)) { const T P = ::tools::pow(p, q); if (::std::gcd(a, p) == 1) { answers.emplace_back(::tools::pow_mod(a, ::tools::tetration_mod(a, b - 1, ::tools::totient(P)), P), P); } else { if (f(a, b - 1) >= q) { answers.emplace_back(0, P); } else { answers.emplace_back(::tools::pow_mod(a, f(a, b - 1), P), P); } } } return ::tools::garner(answers.begin(), answers.end(), m)->first; } } #line 6 "main.cpp" using i64 = std::int_fast64_t; int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); i64 T; std::cin >> T; for (i64 i = 0; i < T; ++i) { i64 A, B, M; std::cin >> A >> B >> M; std::cout << tools::tetration_mod(A, B, M) << '\n'; } return 0; }