結果

問題 No.981 一般冪乗根
ユーザー hashiryohashiryo
提出日時 2022-11-16 01:52:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 6 ms / 6,000 ms
コード長 13,661 bytes
コンパイル時間 2,451 ms
コンパイル使用メモリ 222,964 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-17 00:40:06
合計ジャッジ時間 42,716 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
4,348 KB
testcase_01 AC 3 ms
4,348 KB
testcase_02 AC 3 ms
4,348 KB
testcase_03 AC 3 ms
4,348 KB
testcase_04 AC 3 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 3 ms
4,348 KB
testcase_07 AC 3 ms
4,348 KB
testcase_08 AC 3 ms
4,348 KB
testcase_09 AC 3 ms
4,348 KB
testcase_10 AC 3 ms
4,348 KB
testcase_11 AC 3 ms
4,348 KB
testcase_12 AC 3 ms
4,348 KB
testcase_13 AC 3 ms
4,348 KB
testcase_14 AC 3 ms
4,348 KB
testcase_15 AC 3 ms
4,348 KB
testcase_16 AC 3 ms
4,348 KB
testcase_17 AC 3 ms
4,348 KB
testcase_18 AC 3 ms
4,348 KB
testcase_19 AC 2 ms
4,348 KB
testcase_20 AC 3 ms
4,348 KB
testcase_21 AC 3 ms
4,348 KB
testcase_22 AC 3 ms
4,348 KB
testcase_23 AC 3 ms
4,348 KB
testcase_24 AC 3 ms
4,348 KB
testcase_25 AC 4 ms
4,348 KB
testcase_26 AC 4 ms
4,348 KB
testcase_27 AC 2 ms
4,348 KB
testcase_28 AC 6 ms
4,348 KB
evil_60bit1.txt AC 4 ms
4,348 KB
evil_60bit2.txt AC 3 ms
4,348 KB
evil_60bit3.txt AC 3 ms
4,348 KB
evil_hack AC 2 ms
4,348 KB
evil_hard_random AC 4 ms
4,348 KB
evil_hard_safeprime.txt AC 4 ms
4,348 KB
evil_hard_tonelli0 AC 3 ms
4,348 KB
evil_hard_tonelli1 AC 257 ms
4,348 KB
evil_hard_tonelli2 AC 17 ms
4,348 KB
evil_hard_tonelli3 AC 34 ms
4,348 KB
evil_sefeprime1.txt AC 3 ms
4,348 KB
evil_sefeprime2.txt AC 4 ms
4,348 KB
evil_sefeprime3.txt AC 3 ms
4,348 KB
evil_tonelli1.txt AC 385 ms
4,348 KB
evil_tonelli2.txt AC 388 ms
4,348 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'Int math_internal::peth_root(Int, Int, int, const mod_pro_t&) [with Int = int; mod_pro_t = MIntPro_Na<unsigned int>]':
main.cpp:227:23: warning: argument to variable-length array is too large [-Wvla-larger-than=]
  227 |   std::pair<Int, int> vec[size];
      |                       ^~~
main.cpp:227:23: note: limit is 9223372036854775807 bytes, but argument is 18446744056529682432
main.cpp: In function 'Int math_internal::peth_root(Int, Int, int, const mod_pro_t&) [with Int = long int; mod_pro_t = MIntPro_Montg]':
main.cpp:227:23: warning: argument to variable-length array is too large [-Wvla-larger-than=]
  227 |   std::pair<Int, int> vec[size];
      |                       ^~~
main.cpp:227:23: note: limit is 9223372036854775807 bytes, but argument is 18446744039349813248

ソースコード

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

namespace math_internal {
using namespace std;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;
class MIntPro_Montg {
  const u64 mod, iv, r2;
  constexpr u64 inv(u64 n, int e = 6, u64 x = 1) {
    return e ? inv(n, e - 1, x * (2 - x * n)) : x;
  }
  constexpr u64 reduce(const u128 &w) const {
    return u64(w >> 64) + mod - ((u128(u64(w) * iv) * mod) >> 64);
  }

 public:
  constexpr MIntPro_Montg(u64 m) : mod(m), iv(inv(m)), r2(-u128(mod) % mod) {}
  constexpr u64 mul(u64 l, u64 r) const { return reduce(u128(l) * r); }
#define BOP(op, a) return l op## = a, l += (mod << 1) & -(l >> 63)
  constexpr u64 plus(u64 l, u64 r) const { BOP(+, r - (mod << 1)); }
  constexpr u64 diff(u64 l, u64 r) const { BOP(-, r); }
#undef BOP
  constexpr u64 set(u64 n) const { return mul(n, r2); }
  constexpr u64 get(u64 n) const {
    u64 ret = reduce(n) - mod;
    return ret + (mod & -(ret >> 63));
  }
  constexpr u64 norm(u64 n) const { return n - (mod & -(n >= mod)); }
  constexpr u64 modulo() const { return mod; }
};
template <class Uint>
class MIntPro_Na {
  using DUint = conditional_t<is_same_v<Uint, u32>, u64, u128>;
  const Uint mod;

 public:
  constexpr MIntPro_Na(Uint m) : mod(m) {}
  constexpr Uint mul(Uint l, Uint r) const { return DUint(l) * r % mod; }
#define BOP(m, p) return l m## = mod & -((l p## = r) >= mod)
  constexpr Uint plus(Uint l, Uint r) const { BOP(-, +); }
  constexpr Uint diff(Uint l, Uint r) const { BOP(+, -); }
#undef BOP
  constexpr Uint set(Uint n) const { return n % mod; }
  constexpr Uint get(Uint n) const { return n; }
  constexpr Uint norm(Uint n) const { return n; }
  constexpr Uint modulo() const { return mod; }
};

template <class Uint, class mod_pro_t>
constexpr Uint pow(Uint x, u64 k, const mod_pro_t &md) {
  for (Uint ret = md.set(1);; x = md.mul(x, x))
    if (k & 1 ? ret = md.mul(ret, x) : 0; !(k >>= 1)) return ret;
}
}  // namespace math_internal

namespace math_internal {
template <class Uint, class mod_pro_t, u64... args>
constexpr bool miller_rabin(Uint n) {
  const mod_pro_t md(n);
  const Uint s = __builtin_ctzll(n - 1), d = n >> s, one = md.set(1),
             n1 = md.norm(md.set(n - 1));
  for (auto a : {args...}) {
    Uint b = a % n, p = pow(md.set(b), d, md), i = s;
    while (p = md.norm(p), (p != one && p != n1 && b && i--)) p = md.mul(p, p);
    if (md.norm(p) != n1 && i != s) return false;
  }
  return true;
}
constexpr bool is_prime(u64 n) {
  if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
  if (n < UINT_MAX) return miller_rabin<u32, MIntPro_Na<u32>, 2, 7, 61>(n);
  if (n < LLONG_MAX)
    return miller_rabin<u64, MIntPro_Montg, 2, 325, 9375, 28178, 450775,
                        9780504, 1795265022>(n);
  return miller_rabin<u64, MIntPro_Na<u64>, 2, 325, 9375, 28178, 450775,
                      9780504, 1795265022>(n);
}
}  // namespace math_internal
using math_internal::is_prime;

namespace math_internal {
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, size_t _Nm>
struct ConstexprArray {
  constexpr 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] = {};
  size_t sz = 0;
};
class Factors : public ConstexprArray<pair<u64, uint16_t>, 16> {
  template <class Uint, class mod_pro_t>
  static constexpr Uint rho(Uint n, Uint c) {
    const mod_pro_t md(n);
    auto f = [&md, n, c](Uint x) { return md.plus(md.mul(x, x), c); };
    const Uint m = 1LL << (__lg(n) / 5);
    Uint x = 1, y = md.set(2), z = 1, q = md.set(1), g = 1;
    for (Uint r = 1, i = 0; g == 1; r <<= 1) {
      for (x = y, i = r; i--;) y = f(y);
      for (Uint k = 0; k < r && g == 1; g = gcd(md.get(q), n), k += m)
        for (z = y, i = min(m, r - k); i--;)
          y = f(y), q = md.mul(q, md.diff(y, x));
    }
    if (g == n) do {
        z = f(z), g = gcd(md.get(md.diff(z, x)), n);
      } while (g == 1);
    return g;
  }
  static constexpr u64 find_prime_factor(u64 n) {
    if (is_prime(n)) return n;
    for (u64 i = 100; i--;)
      if (n = n < UINT_MAX    ? rho<u32, MIntPro_Na<u32>>(n, i + 1)
              : n < LLONG_MAX ? rho<u64, MIntPro_Montg>(n, i + 1)
                              : rho<u64, MIntPro_Na<u64>>(n, i + 1);
          is_prime(n))
        return n;
    return 0;
  }
  constexpr void init(u64 n) {
    for (u64 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 (u64 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(u64 n) { init(n), bubble_sort(dat, dat + sz); }
};
template <class Uint, class mod_pro_t>
constexpr Uint inner_primitive_root(Uint p) {
  const mod_pro_t md(p);
  const auto f = Factors(p - 1);
  for (Uint ret = 2, one = md.set(1), pw = 0, x = 0, k = 0, ng = 0;; ret++) {
    for (auto [q, e] : f)
      if (ng = (md.norm(pow(md.set(ret), (p - 1) / q, md)) == one)) break;
    if (!ng) return ret;
  }
}
constexpr u64 primitive_root(u64 p) {
  if (assert(is_prime(p)); p == 2) return 1;
  if (p < UINT_MAX) return inner_primitive_root<u32, MIntPro_Na<u32>>(p);
  if (p < LLONG_MAX) return inner_primitive_root<u64, MIntPro_Montg>(p);
  return inner_primitive_root<u64, MIntPro_Na<u64>>(p);
}
}  // namespace math_internal
using math_internal::Factors, math_internal::primitive_root;

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)); }

template <class Int>
constexpr inline Int mod_inv(Int a, Int mod) {
  static_assert(std::is_signed_v<Int>);
  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;
}

namespace math_internal {
template <class Int, class mod_pro_t>
Int peth_root(Int c, Int pi, int ei, const mod_pro_t &md) {
  const Int p = md.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 = mod_inv(pe - s % pe, pe), ONE = md.set(1),
      z = pow(c, (s * u + 1) / pe, md), zpe = md.norm(pow(c, s * u, md));
  if (zpe == ONE) return z;
  Int ptm1 = 1, vs, base;
  for (int i = t; --i;) ptm1 *= pi;
  for (Int v = md.set(2);; v = md.plus(v, ONE))
    if (vs = pow(v, s, md), base = md.norm(pow(vs, ptm1, md)); base != ONE)
      break;
  int size = 1 << std::__lg(int(std::sqrt(pi)) + 1), mask = size - 1,
      os[size + 1] = {};
  std::pair<Int, int> vec[size];
  Int x = ONE, vspe = pow(vs, pe, md);
  for (int i = 0; i < size; i++, x = md.mul(x, base)) os[md.norm(x) & mask]++;
  for (int i = 1; i < size; i++) os[i] += os[i - 1];
  x = ONE, os[size] = size;
  for (int i = 0; i < size; i++, x = md.norm(md.mul(x, base)))
    vec[--os[x & mask]] = {x, i};
  for (int vs_e = ei, td; zpe != ONE;) {
    Int tmp = zpe;
    for (td = 0; tmp != ONE; td++) tmp = md.norm(pow(tmp, pi, md));
    for (int e = t - td; vs_e != e; vs_e++)
      vs = pow(vs, pi, md), vspe = pow(vspe, pi, md);
    base = md.set(mod_inv<Int>(md.get(zpe), p));
    for (int i = 1; i < td; i++) base = pow(base, pi, md);
    base = md.norm(base);
    for (int tt = 0, upd = 1, n; upd;
         tt += size, base = md.norm(md.mul(base, x)))
      for (int m = (base & mask), i = os[m]; i < os[m + 1]; i++)
        if (base == vec[i].first) {
          if (n = vec[i].second - tt; n < 0) n += pi;
          z = md.mul(z, pow(vs, n, md)),
          zpe = md.norm(md.mul(zpe, pow(vspe, n, md))), upd = false;
          break;
        }
  }
  return z;
}
template <class Int, class mod_pro_t>
Int inner_kth_root(Int a, u64 k, Int p) {
  if (k == 0) return a == 1 ? a : -1;
  if (a <= 1 || k <= 1) return a;
  const mod_pro_t md(p);
  Int g = std::gcd(k, p - 1), ma = md.set(a);
  Int pp = (p - 1) / g, kk = (k / g) % pp;
  if (md.norm(pow(ma, pp, md)) != md.set(1)) return -1;
  ma = pow(ma, mod_inv(kk, pp), md);
  for (auto [pi, ei] : Factors(g)) ma = peth_root<Int>(ma, pi, ei, md);
  return md.get(ma);
}
std::int64_t mod_kth_root(std::int64_t a, u64 k, std::int64_t p) {
  if (a %= p; p < INT_MAX) return inner_kth_root<int, MIntPro_Na<u32>>(a, k, p);
  return inner_kth_root<std::int64_t, MIntPro_Montg>(a, k, p);
}
}  // namespace math_internal
using math_internal::mod_kth_root;

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 << mod_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 << mod_kth_root(a, k, p) << '\n';
  }
  return 0;
}
}  // namespace yukicoder981

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