#683044 (C++17) No.181 A↑↑N mod M

提出ソース
結果

問題	No.181 A↑↑N mod M
ユーザー	anqooqie
提出日時	2021-07-24 03:38:35
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 5,000 ms
コード長	17,706 bytes
コンパイル時間	2,789 ms
コンパイル使用メモリ	227,108 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-07-19 04:15:15
合計ジャッジ時間	3,942 ms
ジャッジサーバーID （参考情報）	judge4 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	1 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	1 ms 5,376 KB
testcase_13	AC	1 ms 5,376 KB
testcase_14	AC	1 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	AC	1 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	2 ms 5,376 KB
testcase_31	AC	1 ms 5,376 KB
testcase_32	AC	2 ms 5,376 KB
testcase_33	AC	2 ms 5,376 KB
testcase_34	AC	2 ms 5,376 KB
testcase_35	AC	1 ms 5,376 KB
testcase_36	AC	2 ms 5,376 KB
testcase_37	AC	2 ms 5,376 KB
testcase_38	AC	2 ms 5,376 KB
testcase_39	AC	1 ms 5,376 KB
testcase_40	AC	2 ms 5,376 KB
testcase_41	AC	2 ms 5,376 KB
testcase_42	AC	2 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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;
}
yukicoder

結果

テストケース

ソースコード
