結果

問題 No.981 一般冪乗根
ユーザー hashiryohashiryo
提出日時 2022-11-13 21:59:44
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 6 ms / 6,000 ms
コード長 17,002 bytes
コンパイル時間 2,921 ms
コンパイル使用メモリ 221,616 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-15 03:24:34
合計ジャッジ時間 49,268 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 3 ms
5,376 KB
testcase_03 AC 4 ms
5,376 KB
testcase_04 AC 4 ms
5,376 KB
testcase_05 AC 4 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 3 ms
5,376 KB
testcase_13 AC 4 ms
5,376 KB
testcase_14 AC 3 ms
5,376 KB
testcase_15 AC 3 ms
5,376 KB
testcase_16 AC 3 ms
5,376 KB
testcase_17 AC 3 ms
5,376 KB
testcase_18 AC 3 ms
5,376 KB
testcase_19 AC 3 ms
5,376 KB
testcase_20 AC 3 ms
5,376 KB
testcase_21 AC 3 ms
5,376 KB
testcase_22 AC 3 ms
5,376 KB
testcase_23 AC 3 ms
5,376 KB
testcase_24 AC 3 ms
5,376 KB
testcase_25 AC 4 ms
5,376 KB
testcase_26 AC 4 ms
5,376 KB
testcase_27 AC 3 ms
5,376 KB
testcase_28 AC 6 ms
5,376 KB
evil_60bit1.txt AC 4 ms
5,376 KB
evil_60bit2.txt AC 4 ms
5,376 KB
evil_60bit3.txt AC 4 ms
5,376 KB
evil_hack AC 2 ms
5,376 KB
evil_hard_random AC 4 ms
5,376 KB
evil_hard_safeprime.txt AC 5 ms
5,376 KB
evil_hard_tonelli0 AC 8 ms
5,376 KB
evil_hard_tonelli1 AC 283 ms
5,376 KB
evil_hard_tonelli2 AC 20 ms
5,376 KB
evil_hard_tonelli3 AC 307 ms
5,376 KB
evil_sefeprime1.txt AC 4 ms
5,376 KB
evil_sefeprime2.txt AC 4 ms
5,376 KB
evil_sefeprime3.txt AC 4 ms
5,376 KB
evil_tonelli1.txt AC 420 ms
5,376 KB
evil_tonelli2.txt AC 417 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#ifndef TEMP
#define TEMP
// clang-format off
template <class T, class U>std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &x) {  return os << "(" << x.first << ", " << x.second << ")";}
template <typename T>std::ostream &operator<<(std::ostream &os, const std::vector<T> &vec) {os << '[';for (int _ = 0, __ = vec.size(); _ < __; _++) os << (_ ? ", " : "") << vec[_];return os << ']';}
template <typename T>std::ostream &operator<<(std::ostream &os, const std::set<T> &s) { os << '{'; int _ = 0; for (const auto &x : s) os << (_++ ? ", " : "") << x; return os << '}';}
template <typename T, std::size_t _Nm>std::ostream &operator<<(std::ostream &os, const std::array<T, _Nm> &arr) {  os << '[' << arr[0];  for (std::size_t _ = 1; _ < _Nm; _++) os << ", " << arr[_];  return os << ']';}
template <class Tup, std::size_t... I>void print(std::ostream &os, const Tup &x, std::index_sequence<I...>) {  using swallow = int[];  (void)swallow{(os << std::get<I>(x) << ", ", 0)...};}
template <class... Args>std::ostream &operator<<(std::ostream &os, const std::tuple<Args...> &x) {  static constexpr std::size_t N = sizeof...(Args);  os << "(";  if constexpr (N >= 2) print(os, x, std::make_index_sequence<N - 1>());  return os << std::get<N - 1>(x) << ")";}
std::ostream &operator<<(std::ostream &os, std::int8_t x) {return os << (int)x;}
std::ostream &operator<<(std::ostream &os, std::uint8_t x) {return os << (int)x;}
std::ostream &operator<<(std::ostream &os, const __int128_t &v) {if (v == 0) os << "0";__int128_t tmp = v < 0 ? (os << "-", -v) : v;std::string s;while (tmp) s += '0' + (tmp % 10), tmp /= 10;return std::reverse(s.begin(), s.end()), os << s;}
std::ostream &operator<<(std::ostream &os, const __uint128_t &v) {if (v == 0) os << "0";__uint128_t tmp = v;std::string s;while (tmp) s += '0' + (tmp % 10), tmp /= 10;return std::reverse(s.begin(), s.end()), os << s;}
#ifdef __LOCAL
const std::string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", ITALIC = "\033[3m", BOLD = "\033[1m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m";
#define func_LINE_FILE  NORMAL_FAINT << " in " << BOLD << __func__ << NORMAL_FAINT << ITALIC << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET
#define checkpoint() std::cerr << BRIGHT_RED << "< check point! >" << func_LINE_FILE << '\n'
#define debug(x) std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << func_LINE_FILE << '\n'
#define debugArray(x, n) do { std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = [" << x[0]; for (int _ = 1; _ < (int)(n); ++_) std::cerr << ", " << x[_]; std::cerr << "]" << func_LINE_FILE << '\n'; } while (0)
#define debugMatrix(x, h, w) do { std::cerr << BRIGHT_CYAN << #x << "\n" << COLOR_RESET << "= "; for (int _ = 0; (_) < (int)(h); ++_) { std::cerr << ((_ ? "   [" : "[[")); for (int __ = 0; __ < (int)(w); ++__) std::cerr << ((__ ? ", " : "")) << x[_][__]; std::cerr << "]" << (_ + 1 == (int)(h) ? "]" : ",\n"); } std::cerr << func_LINE_FILE << '\n'; } while (0)
#else
#define checkpoint() (void(0))
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#define debugMatrix(x, h, w) (void(0))
#endif
template <class T>auto compress(std::vector<T> &v) { std::sort(v.begin(), v.end()); v.erase(std::unique(v.begin(), v.end()), v.end()); return [&v](T x) { return std::lower_bound(v.begin(), v.end(), x) - v.begin(); };}
struct ClosedSection { long long l, r; ClosedSection() : l(1), r(0) {} ClosedSection(long long l_, long long r_) : l(l_), r(r_) {} bool valid() { return l <= r; }};
/* closed [l,r] */ template <class Check> ClosedSection bin_search(const Check &isok, long long l, long long r) { bool res_l = isok(l), res_r = isok(r); if (res_l && res_r) return ClosedSection(l, r); if (!res_l && !res_r) return ClosedSection(); long long lb = l, ub = r; for (long long x; ub - lb > 1;) (isok(x = (lb + ub) / 2) == res_l ? lb : ub) = x; return res_l ? ClosedSection(l, lb) : ClosedSection(ub, r);}
template <class Check> ClosedSection bin_search(const Check &isok, ClosedSection cs) { return cs.valid() ? bin_search(isok, cs.l, cs.r) : cs; }
// clang-format on
#endif

constexpr std::uint64_t mul(std::uint64_t x, std::uint64_t y, std::uint64_t m) {
  return (__uint128_t)x * y % m;
}
template <std::uint64_t... args>
constexpr bool miller_rabin(std::uint64_t n) {
  const std::uint64_t s = __builtin_ctzll(n - 1), d = n >> s;
  for (auto a : {args...}) {
    std::uint64_t b = a % n, p = 1, i = s;
    for (std::uint64_t k = d, x = b;; x = mul(x, x, n))
      if (k & 1 ? p = mul(p, x, n) : 0; !(k >>= 1)) break;
    while (p != 1 && p != n - 1 && b && i--) p = mul(p, p, n);
    if (p != n - 1 && i != s) return false;
  }
  return true;
}
constexpr bool is_prime(std::uint64_t n) {
  if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
  if (n < UINT_MAX) return miller_rabin<2, 7, 61>(n);
  return miller_rabin<2, 325, 9375, 28178, 450775, 9780504, 1795265022>(n);
}

template <class T>
constexpr void bubble_sort(T *bg, T *ed) {
  for (int sz = ed - bg, i = 0; i < sz; i++)
    for (int j = sz; --j > i;)
      if (auto tmp = bg[j - 1]; bg[j - 1] > bg[j])
        bg[j - 1] = bg[j], bg[j] = tmp;
}
template <class T, std::size_t _Nm>
struct ConstexprArray {
  constexpr std::size_t size() const { return sz; }
  constexpr auto &operator[](int i) const { return dat[i]; }
  constexpr auto *begin() const { return dat; }
  constexpr auto *end() const { return dat + sz; }

 protected:
  T dat[_Nm] = {};
  std::size_t sz = 0;
};
class Factors
    : public ConstexprArray<std::pair<std::uint64_t, std::uint16_t>, 16> {
  static constexpr std::uint64_t rho(std::uint64_t n, std::uint64_t c) {
    auto f = [n, c](std::uint64_t x) { return ((__uint128_t)x * x + c) % n; };
    std::uint64_t x = 1, y = 2, z = 1, q = 1, g = 1;
    const std::uint64_t m = 1LL << (std::__lg(n) / 5);
    for (std::uint64_t r = 1, i = 0; g == 1; r <<= 1) {
      for (x = y, i = r; i--;) y = f(y);
      for (std::uint64_t k = 0; k < r && g == 1; g = std::gcd(q, n), k += m)
        for (z = y, i = std::min(m, r - k); i--;)
          y = f(y), q = mul(q, (x > y ? x - y : y - x), n);
    }
    if (g == n) do {
        z = f(z), g = std::gcd((x > z ? x - z : z - x), n);
      } while (g == 1);
    return g;
  }
  static constexpr std::uint64_t find_prime_factor(std::uint64_t n) {
    if (is_prime(n)) return n;
    for (std::uint64_t i = 100, m = 0; i--; n = m)
      if (m = rho(n, i + 1); is_prime(m)) return m;
    return 0;
  }
  constexpr void init(std::uint64_t n) {
    for (std::uint64_t p = 2; p < 100 && p * p <= n; p++)
      if (n % p == 0)
        for (dat[sz++].first = p; n % p == 0;) n /= p, dat[sz - 1].second++;
    for (std::uint64_t p = 0; n > 1; dat[sz++].first = p)
      for (p = find_prime_factor(n); n % p == 0;) n /= p, dat[sz].second++;
  }

 public:
  constexpr Factors() = default;
  constexpr Factors(std::uint64_t n) { init(n), bubble_sort(dat, dat + sz); }
};
constexpr std::uint64_t totient(const Factors &f) {
  std::uint64_t ret = 1, i = 0;
  for (const auto &[p, e] : f)
    for (ret *= p - 1, i = e; --i;) ret *= p;
  return ret;
}
constexpr auto totient(std::uint64_t n) { return totient(Factors(n)); }

constexpr std::uint64_t primitive_root(std::uint64_t p) {
  if (assert(is_prime(p)); p == 2) return 1;
  auto f = Factors(p - 1);
  for (std::uint64_t ret = 2, pw = 0, x = 0, k = 0, ng = 0;; ret++) {
    for (auto [q, e] : f) {
      for (pw = 1, x = ret, k = (p - 1) / q;; x = mul(x, x, p))
        if (k & 1 ? pw = mul(pw, x, p) : 0; !(k >>= 1)) break;
      if (ng = (pw == 1)) break;
    }
    if (!ng) return ret;
  }
}

namespace modint_internal {
using namespace std;
struct modint_base {};
struct sta_mint_base : modint_base {};
struct dyn_mint_base : modint_base {};
template <class mod_t>
constexpr bool is_modint_v = is_base_of_v<modint_base, mod_t>;
template <class mod_t>
constexpr bool is_staticmodint_v = is_base_of_v<sta_mint_base, mod_t>;
template <class mod_t>
constexpr bool is_dynamicmodint_v = is_base_of_v<dyn_mint_base, mod_t>;
using u64 = uint64_t;
using u128 = __uint128_t;
template <class D>
struct ModIntImpl {
  static constexpr inline auto modulo() { return D::mod; }
  constexpr D operator-() const { return D() -= (D &)*this; }
  constexpr D &operator/=(const D &r) { return (D &)*this *= r.inv(); }
  constexpr D operator+(const D &r) const { return D((D &)*this) += r; }
  constexpr D operator-(const D &r) const { return D((D &)*this) -= r; }
  constexpr D operator*(const D &r) const { return D((D &)*this) *= r; }
  constexpr D operator/(const D &r) const { return D((D &)*this) /= r; }
  constexpr bool operator!=(const D &r) const { return !((D &)*this == r); }
  constexpr D pow(u64 k) const {
    for (D ret(1), b((const D &)*this);; b *= b)
      if (k & 1 ? ret *= b : 0; !(k >>= 1)) return ret;
  }
  constexpr D inv() const {
    typename D::Int x = 1, y = 0, a = ((D *)this)->val(), b = D::mod;
    for (typename D::Int q = 0, z = 0, c = 0; b;)
      z = x, c = a, x = y, y = z - y * (q = a / b), a = b, b = c - b * q;
    return assert(a == 1), D(x);
  }
  constexpr bool operator<(const D &r) const {
    return ((D *)this)->val() < r.val();
  }  // for set or map
  friend ostream &operator<<(ostream &os, const D &r) { return os << r.val(); }
  friend istream &operator>>(istream &is, D &r) {
    long long v;
    return is >> v, r = D(v), is;
  }
};
template <class B>
struct ModInt_Na : public B, public ModIntImpl<ModInt_Na<B>> {
  using Int = typename B::Int;
  using DUint = conditional_t<is_same_v<typename B::Uint, uint32_t>, u64, u128>;
  friend ModIntImpl<ModInt_Na<B>>;
  constexpr ModInt_Na() = default;
  template <class T, enable_if_t<is_modint_v<T>, nullptr_t> = nullptr>
  constexpr ModInt_Na(T n) : ModInt_Na(n.val()) {}
  template <class T,
            enable_if_t<is_convertible_v<T, __int128_t>, nullptr_t> = nullptr>
  constexpr ModInt_Na(T n) : x(n < 0 ? B::mod - ((-n) % B::mod) : n % B::mod) {}
#define ASSIGN(m, p) return x m## = B::mod & -((x p## = r.x) >= B::mod), *this
  constexpr ModInt_Na &operator+=(const ModInt_Na &r) { ASSIGN(-, +); }
  constexpr ModInt_Na &operator-=(const ModInt_Na &r) { ASSIGN(+, -); }
#undef ASSIGN
  constexpr ModInt_Na &operator*=(const ModInt_Na &r) {
    return x = (DUint)(x)*r.x % B::mod, *this;
  }
  constexpr bool operator==(const ModInt_Na &r) const { return x == r.x; }
  constexpr auto val() const { return x; }

 private:
  typename B::Uint x = 0;
};
template <class B>
struct ModInt_Mon : public B, public ModIntImpl<ModInt_Mon<B>> {
  using Int = int64_t;
  using mod_t = ModInt_Mon;
  friend ModIntImpl<ModInt_Mon<B>>;
  constexpr ModInt_Mon() = default;
  template <class T, enable_if_t<is_modint_v<T>, nullptr_t> = nullptr>
  constexpr ModInt_Mon(T n) : ModInt_Mon(n.val()) {}
  template <class T,
            enable_if_t<is_convertible_v<T, __int128_t>, nullptr_t> = nullptr>
  constexpr ModInt_Mon(T n)
      : x(mul(n < 0 ? B::mod - ((-n) % B::mod) : n % B::mod, B::r2)) {}
#define ASGN(op, a) return x op## = a, x += (B::mod << 1) & -(x >> 63), *this
  constexpr mod_t &operator+=(const mod_t &r) { ASGN(+, r.x - (B::mod << 1)); }
  constexpr mod_t &operator-=(const mod_t &r) { ASGN(-, r.x); }
#undef ASGN
  constexpr mod_t &operator*=(const mod_t &r) { return x = mul(x, r.x), *this; }
  constexpr bool operator==(const mod_t &r) const { return norm() == r.norm(); }
  constexpr u64 val() const {
    u64 ret = reduce(x) - B::mod;
    return ret + (B::mod & -(ret >> 63));
  }

 private:
  static constexpr inline u64 reduce(const u128 &w) {
    return u64(w >> 64) + B::mod - ((u128(u64(w) * B::iv) * B::mod) >> 64);
  }
  static constexpr inline u64 mul(u64 l, u64 r) { return reduce(u128(l) * r); }
  u64 x = 0;
  constexpr inline u64 norm() const { return x - (B::mod & -(x >= B::mod)); }
};
constexpr u64 mul_inv(u64 n, int e = 6, u64 x = 1) {
  return e ? mul_inv(n, e - 1, x * (2 - x * n)) : x;
}
template <u64 MOD>
struct StaticB_Na : sta_mint_base {
 protected:
  using Int = conditional_t < MOD < INT_MAX, int32_t,
        conditional_t<MOD<LLONG_MAX, int64_t, __int128_t>>;
  using Uint = conditional_t < MOD < INT_MAX, uint32_t,
        conditional_t<MOD<LLONG_MAX, u64, u128>>;
  static constexpr Uint mod = MOD;
};
template <u64 MOD>
struct StaticB_Mon : sta_mint_base {
 protected:
  static_assert(MOD & 1);
  static constexpr u64 mod = MOD, iv = mul_inv(mod), r2 = -u128(mod) % mod;
};
template <class I, int id = -1>
struct DynamicB_Na : dyn_mint_base {
  static_assert(is_integral_v<I>);
  static inline void set_mod(I m) { mod = m; }

 protected:
  using Int = I;
  using Uint = make_unsigned_t<Int>;
  static inline Uint mod;
};
template <int id>
struct DynamicB_Mon : dyn_mint_base {
  static inline void set_mod(u64 m) {
    assert(m & 1), iv = mul_inv(mod = m), r2 = -u128(m) % m;
  }

 protected:
  static inline u64 mod, iv, r2;
};
template <u64 mod>
using StaticModInt =
    conditional_t<mod &(INT_MAX <= mod) & (mod < LLONG_MAX),
                  ModInt_Mon<StaticB_Mon<mod>>, ModInt_Na<StaticB_Na<mod>>>;
struct Montgomery {};
template <class Int, int id = -1>
using DynamicModInt =
    conditional_t<is_same_v<Int, Montgomery>, ModInt_Mon<DynamicB_Mon<id>>,
                  ModInt_Na<DynamicB_Na<Int, id>>>;
}  // namespace modint_internal
using modint_internal::DynamicModInt, modint_internal::StaticModInt,
    modint_internal::Montgomery, modint_internal::is_dynamicmodint_v,
    modint_internal::is_modint_v, modint_internal::is_staticmodint_v;
template <class mod_t, std::size_t LIM>
mod_t get_inv(int n) {
  static_assert(is_modint_v<mod_t>);
  static const auto m = mod_t::modulo();
  static mod_t dat[LIM];
  static int l = 1;
  if (l == 1) dat[l++] = 1;
  while (l <= n) dat[l++] = dat[m % l] * (m - m / l);
  return dat[n];
}

template <class Int>
inline Int inv_mod(Int a, Int mod) {
  Int x = 1, y = 0, b = mod;
  for (Int q = 0, z = 0, c = 0; b;)
    z = x, c = a, x = y, y = z - y * (q = a / b), a = b, b = c - b * q;
  return assert(a == 1), x < 0 ? mod - (-x) % mod : x % mod;
}

template <class Int, class mod_t>
mod_t peth_root(mod_t c, Int pi, int ei) {
  const Int p = mod_t::modulo();
  int t = 0;
  Int s = p - 1, pe = 1;
  while (s % pi == 0) s /= pi, ++t;
  for (int i = ei; i--;) pe *= pi;
  Int u = inv_mod(pe - s % pe, pe);
  mod_t ONE = 1, z = c.pow((s * u + 1) / pe), zpe = c.pow(s * u);
  if (zpe == ONE) return z;
  Int ptm1 = 1;
  for (int i = t; --i;) ptm1 *= pi;
  mod_t vs, base;
  for (mod_t v = 2;; v += ONE)
    if (vs = v.pow(s), base = vs.pow(ptm1); base != ONE) break;

  int size = 1 << std::__lg(int(std::sqrt(pi * (t - ei))) + 1), mask = size - 1;
  std::vector<std::pair<mod_t, int>> vec(size);
  std::vector<int> os(size + 1);
  mod_t x = 1, vspe = vs.pow(pe);
  for (int i = 0; i < size; ++i, x *= base) os[x.val() & mask]++;
  for (int i = 1; i < size; ++i) os[i] += os[i - 1];
  x = 1;
  for (int i = 0; i < size; ++i, x *= base) vec[--os[x.val() & mask]] = {x, i};
  os[size] = size;

  for (int vs_e = ei, td; zpe != ONE;) {
    mod_t tmp = zpe, base_zpe = mod_t(1) / zpe;
    for (td = 0; tmp != ONE; td++) tmp = tmp.pow(pi);
    for (int e = t - td; vs_e != e; vs_e++)
      vs = vs.pow(pi), vspe = vspe.pow(pi);
    for (int i = td; --i;) base_zpe = base_zpe.pow(pi);
    for (int tt = 0, upd = 1, n; upd; tt += size, base_zpe *= x)
      for (int m = (base_zpe.val() & mask), i = os[m]; i < os[m + 1]; i++)
        if (base_zpe == vec[i].first) {
          if (n = vec[i].second - tt; n < 0) n += pi;
          z *= vs.pow(n), zpe *= vspe.pow(n), upd = false;
          break;
        }
  }
  return z;
}

template <class Int, class mod_t>
Int inner_kth_root(Int a, std::uint64_t k, Int p) {
  if (k == 0) return a == 1 ? a : -1;
  if (a <= 1 || k <= 1) return a;
  mod_t::set_mod(p);
  Int g = std::gcd(k, p - 1);
  mod_t ma = a;
  Int pp = (p - 1) / g, kk = (k / g) % pp;
  if (ma.pow(pp) != mod_t(1)) return -1;
  ma = ma.pow(inv_mod(kk, pp));
  for (auto [pi, ei] : Factors(g)) ma = peth_root<Int>(ma, pi, ei);
  return ma.val();
}

std::int64_t kth_root(std::int64_t a, std::uint64_t k, std::int64_t p) {
  if (a %= p; p < INT_MAX)
    return inner_kth_root<int, DynamicModInt<int, -2>>(a, k, p);
  else
    return inner_kth_root<std::int64_t, DynamicModInt<Montgomery, -2>>(a, k, p);
}

using namespace std;
namespace yosupo_kth_root {
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) {
    int K, Y, P;
    cin >> K >> Y >> P;
    cout << kth_root(Y, K, P) << '\n';
  }
  return 0;
}
}  // namespace yosupo_kth_root

namespace yukicoder981 {
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) {
    std::int64_t p, k, a;
    cin >> p >> k >> a;
    cout << kth_root(a, k, p) << '\n';
  }
  return 0;
}
}  // namespace yukicoder981

signed main() {
  // yosupo_kth_root::main();
  yukicoder981::main();
  return 0;
}
0