結果
| 問題 |
No.181 A↑↑N mod M
|
| コンテスト | |
| ユーザー |
 anqooqie
|
| 提出日時 | 2021-07-24 03:38:35 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 5,000 ms |
| コード長 | 17,706 bytes |
| コンパイル時間 | 2,426 ms |
| コンパイル使用メモリ | 219,336 KB |
| 最終ジャッジ日時 | 2025-01-23 09:21:13 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 6 |
| other | AC * 37 |
ソースコード
#line 1 "/home/anqooqie/.proconlib/tools/util.hpp"
// To see the details of my library, visit my GitHub Pages.
// https://anqooqie.github.io/proconlib/
#ifdef LOCAL
#ifndef _GLIBCXX_DEBUG
#define _GLIBCXX_DEBUG
#endif
#else
#ifndef NDEBUG
#define NDEBUG
#endif
#endif
#include <bits/stdc++.h>
#line 1 "/home/anqooqie/.proconlib/tools/resize.hpp"
#line 5 "/home/anqooqie/.proconlib/tools/resize.hpp"
// Source: https://koyumeishi.hatenablog.com/entry/2016/02/01/152426
// License: unknown
// Author: koyumeishi
namespace tools {
template <class T, class Allocator, typename Head>
void resize(::std::vector<T, Allocator>& vector, const Head& head) {
vector.resize(head);
}
template <class T, class Allocator, typename Head, typename... Tail>
void resize(::std::vector<T, Allocator>& vector, const Head& head, const Tail&... tail) {
vector.resize(head);
for (auto& child : vector) {
::tools::resize(child, tail...);
}
}
}
#line 1 "/home/anqooqie/.proconlib/tools/fill.hpp"
#line 5 "/home/anqooqie/.proconlib/tools/fill.hpp"
#include <type_traits>
#line 1 "/home/anqooqie/.proconlib/tools/is_range.hpp"
#line 7 "/home/anqooqie/.proconlib/tools/is_range.hpp"
namespace tools {
template <typename T>
class is_range {
private:
template <typename U>
static auto check(U x) -> decltype(::std::begin(x), ::std::end(x), ::std::true_type{});
static ::std::false_type check(...);
public:
static const bool value = decltype(check(::std::declval<T>()))::value;
};
}
#line 9 "/home/anqooqie/.proconlib/tools/fill.hpp"
namespace tools {
template <class T, class Allocator, typename V>
auto fill(::std::vector<T, Allocator>& vector, const V& value) -> ::std::enable_if_t<!::tools::is_range<T>::value, void> {
::std::fill(::std::begin(vector), ::std::end(vector), value);
}
template <class T, class Allocator, typename V>
auto fill(::std::vector<T, Allocator>& vector, const V& value) -> ::std::enable_if_t<::tools::is_range<T>::value, void> {
for (auto& child : vector) {
::tools::fill(child, value);
}
}
}
#line 20 "/home/anqooqie/.proconlib/tools/util.hpp"
using i64 = ::std::int_fast64_t;
using u64 = ::std::uint_fast64_t;
using i32 = ::std::int_fast32_t;
using u32 = ::std::uint_fast32_t;
#define ALL(x) ::std::begin((x)), ::std::end((x))
namespace tools {
namespace detail {
namespace util {
template <typename T>
class has_val {
private:
template <typename U>
static auto check(U x) -> decltype(x.val(), ::std::true_type{});
static ::std::false_type check(...);
public:
static const bool value = decltype(check(::std::declval<T>()))::value;
};
template <typename T>
::std::istream& read(::std::istream& is, T& container) {
for (auto& v : container) {
is >> v;
}
return is;
}
template <typename T>
::std::ostream& debug_print(::std::ostream& os, const T& container) {
::std::string delimiter = "";
os << '[';
for (const auto& v : container) {
os << delimiter << v;
delimiter = ", ";
}
os << ']';
return os;
}
}
}
}
template <class T, class Allocator>
::std::istream& operator>>(::std::istream& is, ::std::vector<T, Allocator>& vector) {
return ::tools::detail::util::read(is, vector);
}
template <class T, ::std::size_t N>
::std::istream& operator>>(::std::istream& is, ::std::array<T, N>& array) {
return ::tools::detail::util::read(is, array);
}
template <class T, class Allocator>
::std::ostream& operator<<(::std::ostream& os, const ::std::vector<T, Allocator>& vector) {
return ::tools::detail::util::debug_print(os, vector);
}
template <class T, ::std::size_t N>
::std::ostream& operator<<(::std::ostream& os, const ::std::array<T, N>& array) {
return ::tools::detail::util::debug_print(os, array);
}
template <class Key, class Hash, class Pred, class Allocator>
::std::ostream& operator<<(::std::ostream& os, const ::std::unordered_set<Key, Hash, Pred, Allocator>& unordered_set) {
return ::tools::detail::util::debug_print(os, unordered_set);
}
template <class T, class Container>
::std::ostream& operator<<(::std::ostream& os, ::std::stack<T, Container>& stack) {
::std::stack<T, Container> other;
::std::string delimiter = "";
os << '[';
while (!stack.empty()) {
os << delimiter << stack.top();
delimiter = ", ";
other.push(stack.top());
stack.pop();
}
os << ']';
while (!other.empty()) {
stack.push(other.top());
other.pop();
}
return os;
}
template <class T, class Container>
::std::ostream& operator<<(::std::ostream& os, ::std::queue<T, Container>& queue) {
::std::queue<T, Container> other = queue;
::std::string delimiter = "";
os << '[';
while (!queue.empty()) {
os << delimiter << queue.front();
delimiter = ", ";
queue.pop();
}
os << ']';
queue = ::std::move(other);
return os;
}
template <class T1, class T2>
::std::ostream& operator<<(::std::ostream& os, const ::std::pair<T1, T2>& pair) {
return os << '[' << pair.first << ", " << pair.second << ']';
}
template <int I = -1, typename... Args>
::std::ostream& operator<<(::std::ostream& os, const ::std::tuple<Args...>& tuple) {
if constexpr (I == -1) {
os << '[';
} else if constexpr (I == int(sizeof...(Args))) {
os << ']';
} else if constexpr (I == 0) {
os << ::std::get<I>(tuple);
} else {
os << ", " << ::std::get<I>(tuple);
}
if constexpr (I < int(sizeof...(Args))) {
return operator<<<I + 1>(os, tuple);
} else {
return os;
}
}
template <typename T>
auto operator<<(::std::ostream& os, const T& x) -> ::std::enable_if_t<::tools::detail::util::has_val<T>::value, ::std::ostream&> {
return os << x.val();
}
#line 1 "/home/anqooqie/.proconlib/tools/tetration_mod.hpp"
#line 1 "/home/anqooqie/.proconlib/tools/pow.hpp"
#line 1 "/home/anqooqie/.proconlib/tools/monoid.hpp"
#line 7 "/home/anqooqie/.proconlib/tools/monoid.hpp"
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"
#line 1 "/home/anqooqie/.proconlib/tools/is_prime.hpp"
#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"
#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 1 "/home/anqooqie/.proconlib/tools/inv_mod.hpp"
#line 1 "/home/anqooqie/.proconlib/tools/extgcd.hpp"
#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 3 "main.cpp"
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
i64 A, N, M;
std::cin >> A >> N >> M;
std::cout << tools::tetration_mod(A, N, M) << '\n';
return 0;
}