結果

問題 No.981 一般冪乗根
ユーザー NyaanNyaanNyaanNyaan
提出日時 2020-09-18 20:26:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 11 ms / 6,000 ms
コード長 19,042 bytes
コンパイル時間 3,947 ms
コンパイル使用メモリ 326,172 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-22 08:14:55
合計ジャッジ時間 64,433 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#pragma region kyopro_template
#define Nyaan_template
#include <immintrin.h>
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define each(x, v) for (auto &x : v)
#define all(v) (v).begin(), (v).end()
#define sz(v) ((int)(v).size())
#define mem(a, val) memset(a, val, sizeof(a))
#define ini(...)   \
  int __VA_ARGS__; \
  in(__VA_ARGS__)
#define inl(...)         \
  long long __VA_ARGS__; \
  in(__VA_ARGS__)
#define ins(...)      \
  string __VA_ARGS__; \
  in(__VA_ARGS__)
#define inc(...)    \
  char __VA_ARGS__; \
  in(__VA_ARGS__)
#define in2(s, t)                           \
  for (int i = 0; i < (int)s.size(); i++) { \
    in(s[i], t[i]);                         \
  }
#define in3(s, t, u)                        \
  for (int i = 0; i < (int)s.size(); i++) { \
    in(s[i], t[i], u[i]);                   \
  }
#define in4(s, t, u, v)                     \
  for (int i = 0; i < (int)s.size(); i++) { \
    in(s[i], t[i], u[i], v[i]);             \
  }
#define rep(i, N) for (long long i = 0; i < (long long)(N); i++)
#define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--)
#define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++)
#define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--)
#define reg(i, a, b) for (long long i = (a); i < (b); i++)
#define die(...)      \
  do {                \
    out(__VA_ARGS__); \
    return;           \
  } while (0)
using namespace std;
using ll = long long;
template <class T>
using V = vector<T>;
using vi = vector<int>;
using vl = vector<long long>;
using vvi = vector<vector<int>>;
using vd = V<double>;
using vs = V<string>;
using vvl = vector<vector<long long>>;
using P = pair<long long, long long>;
using vp = vector<P>;
using pii = pair<int, int>;
using vpi = vector<pair<int, int>>;
constexpr int inf = 1001001001;
constexpr long long infLL = (1LL << 61) - 1;
template <typename T, typename U>
inline bool amin(T &x, U y) {
  return (y < x) ? (x = y, true) : false;
}
template <typename T, typename U>
inline bool amax(T &x, U y) {
  return (x < y) ? (x = y, true) : false;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << p.first << " " << p.second;
  return os;
}
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p) {
  is >> p.first >> p.second;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  int s = (int)v.size();
  for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];
  return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (auto &x : v) is >> x;
  return is;
}
void in() {}
template <typename T, class... U>
void in(T &t, U &... u) {
  cin >> t;
  in(u...);
}
void out() { cout << "\n"; }
template <typename T, class... U>
void out(const T &t, const U &... u) {
  cout << t;
  if (sizeof...(u)) cout << " ";
  out(u...);
}

#ifdef NyaanDebug
#define trc(...)                   \
  do {                             \
    cerr << #__VA_ARGS__ << " = "; \
    dbg_out(__VA_ARGS__);          \
  } while (0)
#define trca(v, N)       \
  do {                   \
    cerr << #v << " = "; \
    array_out(v, N);     \
  } while (0)
#define trcc(v)                             \
  do {                                      \
    cerr << #v << " = {";                   \
    each(x, v) { cerr << " " << x << ","; } \
    cerr << "}" << endl;                    \
  } while (0)
template <typename T>
void _cout(const T &c) {
  cerr << c;
}
void _cout(const int &c) {
  if (c == 1001001001)
    cerr << "inf";
  else if (c == -1001001001)
    cerr << "-inf";
  else
    cerr << c;
}
void _cout(const unsigned int &c) {
  if (c == 1001001001)
    cerr << "inf";
  else
    cerr << c;
}
void _cout(const long long &c) {
  if (c == 1001001001 || c == (1LL << 61) - 1)
    cerr << "inf";
  else if (c == -1001001001 || c == -((1LL << 61) - 1))
    cerr << "-inf";
  else
    cerr << c;
}
void _cout(const unsigned long long &c) {
  if (c == 1001001001 || c == (1LL << 61) - 1)
    cerr << "inf";
  else
    cerr << c;
}
template <typename T, typename U>
void _cout(const pair<T, U> &p) {
  cerr << "{ ";
  _cout(p.fi);
  cerr << ", ";
  _cout(p.se);
  cerr << " } ";
}
template <typename T>
void _cout(const vector<T> &v) {
  int s = v.size();
  cerr << "{ ";
  for (int i = 0; i < s; i++) {
    cerr << (i ? ", " : "");
    _cout(v[i]);
  }
  cerr << " } ";
}
template <typename T>
void _cout(const vector<vector<T>> &v) {
  cerr << "[ ";
  for (const auto &x : v) {
    cerr << endl;
    _cout(x);
    cerr << ", ";
  }
  cerr << endl << " ] ";
}
void dbg_out() { cerr << endl; }
template <typename T, class... U>
void dbg_out(const T &t, const U &... u) {
  _cout(t);
  if (sizeof...(u)) cerr << ", ";
  dbg_out(u...);
}
template <typename T>
void array_out(const T &v, int s) {
  cerr << "{ ";
  for (int i = 0; i < s; i++) {
    cerr << (i ? ", " : "");
    _cout(v[i]);
  }
  cerr << " } " << endl;
}
template <typename T>
void array_out(const T &v, int H, int W) {
  cerr << "[ ";
  for (int i = 0; i < H; i++) {
    cerr << (i ? ", " : "");
    array_out(v[i], W);
  }
  cerr << " ] " << endl;
}
#else
#define trc(...)
#define trca(...)
#define trcc(...)
#endif

inline int popcnt(unsigned long long a) { return __builtin_popcountll(a); }
inline int lsb(unsigned long long a) { return __builtin_ctzll(a); }
inline int msb(unsigned long long a) { return 63 - __builtin_clzll(a); }
template <typename T>
inline int getbit(T a, int i) {
  return (a >> i) & 1;
}
template <typename T>
inline void setbit(T &a, int i) {
  a |= (1LL << i);
}
template <typename T>
inline void delbit(T &a, int i) {
  a &= ~(1LL << i);
}
template <typename T>
int lb(const vector<T> &v, const T &a) {
  return lower_bound(begin(v), end(v), a) - begin(v);
}
template <typename T>
int ub(const vector<T> &v, const T &a) {
  return upper_bound(begin(v), end(v), a) - begin(v);
}
template <typename T>
int btw(T a, T x, T b) {
  return a <= x && x < b;
}
template <typename T, typename U>
T ceil(T a, U b) {
  return (a + b - 1) / b;
}
constexpr long long TEN(int n) {
  long long ret = 1, x = 10;
  while (n) {
    if (n & 1) ret *= x;
    x *= x;
    n >>= 1;
  }
  return ret;
}
template <typename T>
vector<T> mkrui(const vector<T> &v) {
  vector<T> ret(v.size() + 1);
  for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i];
  return ret;
};
template <typename T>
vector<T> mkuni(const vector<T> &v) {
  vector<T> ret(v);
  sort(ret.begin(), ret.end());
  ret.erase(unique(ret.begin(), ret.end()), ret.end());
  return ret;
}
template <typename F>
vector<int> mkord(int N, F f) {
  vector<int> ord(N);
  iota(begin(ord), end(ord), 0);
  sort(begin(ord), end(ord), f);
  return ord;
}
template <typename T = int>
vector<T> mkiota(int N) {
  vector<T> ret(N);
  iota(begin(ret), end(ret), 0);
  return ret;
}
template <typename T>
vector<int> mkinv(vector<T> &v) {
  vector<int> inv(v.size());
  for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i;
  return inv;
}

struct IoSetupNya {
  IoSetupNya() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(7);
  }
} iosetupnya;

void solve();
int main() { solve(); }

#pragma endregion
using namespace std;

namespace inner {

using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

template <typename T>
T gcd(T a, T b) {
  while (b) swap(a %= b, b);
  return a;
}

template <typename T>
T inv(T a, T p) {
  T b = p, x = 1, y = 0;
  while (a) {
    T q = b / a;
    swap(a, b %= a);
    swap(x, y -= q * x);
  }
  assert(b == 1);
  return y < 0 ? y + p : y;
}

template <typename T, typename U>
T modpow(T a, U n, T p) {
  T ret = 1 % p;
  for (; n; n >>= 1, a = U(a) * a % p)
    if (n & 1) ret = U(ret) * a % p;
  return ret;
}

}  // namespace inner

using namespace std;

using namespace std;

unsigned long long rng() {
  static unsigned long long x_ = 88172645463325252ULL;
  x_ = x_ ^ (x_ << 7);
  return x_ = x_ ^ (x_ >> 9);
}using namespace std;

struct ArbitraryLazyMontgomeryModInt {
  using mint = ArbitraryLazyMontgomeryModInt;
  using i32 = int32_t;
  using u32 = uint32_t;
  using u64 = uint64_t;

  static u32 mod;
  static u32 r;
  static u32 n2;

  static u32 get_r() {
    u32 ret = mod;
    for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret;
    return ret;
  }

  static void set_mod(u32 m) {
    assert(m < (1 << 30));
    assert((m & 1) == 1);
    mod = m;
    n2 = -u64(m) % m;
    r = get_r();
    assert(r * mod == 1);
  }

  u32 a;

  ArbitraryLazyMontgomeryModInt() : a(0) {}
  ArbitraryLazyMontgomeryModInt(const int64_t &b)
      : a(reduce(u64(b % mod + mod) * n2)){};

  static u32 reduce(const u64 &b) {
    return (b + u64(u32(b) * u32(-r)) * mod) >> 32;
  }

  mint &operator+=(const mint &b) {
    if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod;
    return *this;
  }

  mint &operator-=(const mint &b) {
    if (i32(a -= b.a) < 0) a += 2 * mod;
    return *this;
  }

  mint &operator*=(const mint &b) {
    a = reduce(u64(a) * b.a);
    return *this;
  }

  mint &operator/=(const mint &b) {
    *this *= b.inverse();
    return *this;
  }

  mint operator+(const mint &b) const { return mint(*this) += b; }
  mint operator-(const mint &b) const { return mint(*this) -= b; }
  mint operator*(const mint &b) const { return mint(*this) *= b; }
  mint operator/(const mint &b) const { return mint(*this) /= b; }
  bool operator==(const mint &b) const {
    return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);
  }
  bool operator!=(const mint &b) const {
    return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);
  }
  mint operator-() const { return mint() - mint(*this); }

  mint pow(u64 n) const {
    mint ret(1), mul(*this);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  friend ostream &operator<<(ostream &os, const mint &b) {
    return os << b.get();
  }

  friend istream &operator>>(istream &is, mint &b) {
    int64_t t;
    is >> t;
    b = ArbitraryLazyMontgomeryModInt(t);
    return (is);
  }

  mint inverse() const { return pow(mod - 2); }

  u32 get() const {
    u32 ret = reduce(a);
    return ret >= mod ? ret - mod : ret;
  }

  static u32 get_mod() { return mod; }
};
typename ArbitraryLazyMontgomeryModInt::u32 ArbitraryLazyMontgomeryModInt::mod;
typename ArbitraryLazyMontgomeryModInt::u32 ArbitraryLazyMontgomeryModInt::r;
typename ArbitraryLazyMontgomeryModInt::u32 ArbitraryLazyMontgomeryModInt::n2;
using namespace std;

struct montgomery64 {
  using mint = montgomery64;
  using i64 = int64_t;
  using u64 = uint64_t;
  using u128 = __uint128_t;

  static u64 mod;
  static u64 r;
  static u64 n2;

  static u64 get_r() {
    u64 ret = mod;
    for (i64 i = 0; i < 5; ++i) ret *= 2 - mod * ret;
    return ret;
  }

  static void set_mod(u64 m) {
    assert(m < (1LL << 62));
    assert((m & 1) == 1);
    mod = m;
    n2 = -u128(m) % m;
    r = get_r();
    assert(r * mod == 1);
  }

  u64 a;

  montgomery64() : a(0) {}
  montgomery64(const int64_t &b) : a(reduce((u128(b) + mod) * n2)){};

  static u64 reduce(const u128 &b) {
    return (b + u128(u64(b) * u64(-r)) * mod) >> 64;
  }

  mint &operator+=(const mint &b) {
    if (i64(a += b.a - 2 * mod) < 0) a += 2 * mod;
    return *this;
  }

  mint &operator-=(const mint &b) {
    if (i64(a -= b.a) < 0) a += 2 * mod;
    return *this;
  }

  mint &operator*=(const mint &b) {
    a = reduce(u128(a) * b.a);
    return *this;
  }

  mint &operator/=(const mint &b) {
    *this *= b.inverse();
    return *this;
  }

  mint operator+(const mint &b) const { return mint(*this) += b; }
  mint operator-(const mint &b) const { return mint(*this) -= b; }
  mint operator*(const mint &b) const { return mint(*this) *= b; }
  mint operator/(const mint &b) const { return mint(*this) /= b; }
  bool operator==(const mint &b) const {
    return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);
  }
  bool operator!=(const mint &b) const {
    return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);
  }
  mint operator-() const { return mint() - mint(*this); }

  mint pow(u128 n) const {
    mint ret(1), mul(*this);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  friend ostream &operator<<(ostream &os, const mint &b) {
    return os << b.get();
  }

  friend istream &operator>>(istream &is, mint &b) {
    int64_t t;
    is >> t;
    b = montgomery64(t);
    return (is);
  }

  mint inverse() const { return pow(mod - 2); }

  u64 get() const {
    u64 ret = reduce(a);
    return ret >= mod ? ret - mod : ret;
  }

  static u64 get_mod() { return mod; }
};
typename montgomery64::u64 montgomery64::mod, montgomery64::r, montgomery64::n2;

namespace fast_factorize {
using u64 = uint64_t;

template <typename mint>
bool miller_rabin(u64 n, vector<u64> as) {
  if (mint::get_mod() != n) mint::set_mod(n);
  u64 d = n - 1;
  while (~d & 1) d >>= 1;
  mint e{1}, rev{int64_t(n - 1)};
  for (u64 a : as) {
    if (n <= a) break;
    u64 t = d;
    mint y = mint(a).pow(t);
    while (t != n - 1 && y != e && y != rev) {
      y *= y;
      t *= 2;
    }
    if (y != rev && t % 2 == 0) return false;
  }
  return true;
}

bool is_prime(u64 n) {
  if (~n & 1) return n == 2;
  if (n <= 1) return false;
  if (n < (1LL << 30))
    return miller_rabin<ArbitraryLazyMontgomeryModInt>(n, {2, 7, 61});
  else
    return miller_rabin<montgomery64>(
        n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
}

template <typename mint, typename T>
T pollard_rho(T n) {
  if (~n & 1) return 2;
  if (is_prime(n)) return n;
  if (mint::get_mod() != n) mint::set_mod(n);
  mint R, one = 1;
  auto f = [&](mint x) { return x * x + R; };
  auto rnd = [&]() { return rng() % (n - 2) + 2; };
  while (1) {
    mint x, y, ys, q = one;
    R = rnd(), y = rnd();
    T g = 1;
    constexpr int m = 128;
    for (int r = 1; g == 1; r <<= 1) {
      x = y;
      for (int i = 0; i < r; ++i) y = f(y);
      for (int k = 0; g == 1 && k < r; k += m) {
        ys = y;
        for (int i = 0; i < m && i < r - k; ++i) q *= x - (y = f(y));
        g = inner::gcd<T>(q.get(), n);
      }
    }
    if (g == n) do
        g = inner::gcd<T>((x - (ys = f(ys))).get(), n);
      while (g == 1);
    if (g != n) return g;
  }
  exit(1);
}

vector<u64> inner_factorize(u64 n) {
  if (n <= 1) return {};
  u64 p;
  if (n <= (1LL << 30))
    p = pollard_rho<ArbitraryLazyMontgomeryModInt, uint32_t>(n);
  else
    p = pollard_rho<montgomery64, uint64_t>(n);
  if (p == n) return {p};
  auto l = inner_factorize(p);
  auto r = inner_factorize(n / p);
  copy(begin(r), end(r), back_inserter(l));
  return l;
}

vector<u64> factorize(u64 n) {
  auto ret = inner_factorize(n);
  sort(begin(ret), end(ret));
  return ret;
}

}  // namespace fast_factorize
using fast_factorize::factorize;
using fast_factorize::is_prime;

/**
 * @brief 高速素因数分解(Miller Rabin/Pollard's Rho)
 * @docs docs/prime/fast-factorize.md
 */

namespace kth_root_mod {
using inner::gcd;
using inner::inv;
using inner::modpow;
template <typename INT, typename LINT>
INT pe_root(INT c, INT pi, INT ei, INT p) {
  INT s = p - 1, t = 0;
  while (s % pi == 0) s /= pi, ++t;
  INT pe = 1;
  for (INT _ = 0; _ < ei; ++_) pe *= pi;
  INT u = inv(pe - s % pe, pe);
  INT z = modpow<INT, LINT>(c, (s * u + 1) / pe, p);
  INT zpe = modpow<INT, LINT>(c, s * u, p);
  if (zpe == 1) return z;
  INT vs = -1, ptm1 = 1;
  for (INT _ = 0; _ < t - 1; ++_) ptm1 *= pi;
  for (INT v = 2;; ++v) {
    vs = modpow<INT, LINT>(v, s, p);
    if (modpow<INT, LINT>(vs, ptm1, p) != 1) break;
  }
  INT vspe = modpow<INT, LINT>(vs, pe, p);
  INT vs_e = ei;
  unordered_map<INT, INT> memo;
  INT m = sqrt(t - ei + 1) * sqrt(pi), offset;
  // trc(t, ei, p);
  // trc("med", vs, vspe, vs_e, m);
  {
    INT base = vspe;
    for (INT _ = 0; _ < t - ei - 1; _++) base = modpow<INT, LINT>(base, pi, p);
    offset = modpow<INT, LINT>(inv(base, p), m, p);
    INT cvs = 1;
    for (INT i = 0; i < m; i++) {
      memo[cvs] = i;
      cvs = LINT(cvs) * base % p;
      if (cvs == 1) break;
    }
  }
  while (zpe != 1) {
    INT tmp = zpe, td = 0;
    while (tmp != 1) ++td, tmp = modpow<INT, LINT>(tmp, pi, p);
    INT e = t - td;
    while (vs_e != e) {
      vs = modpow<INT, LINT>(vs, pi, p);
      vspe = modpow<INT, LINT>(vspe, pi, p);
      ++vs_e;
    }
    // BS-GS ... find (zpe * ( vspe ^ n ) ) ^( p_i ^ (td - 1) ) = 1
    // memo[n] = vs ^ n ^ ( p_i ^ (td - 1) )
    INT bsgs = -1;
    {
      INT base_zpe = inv(zpe, p);
      for (INT _ = 0; _ < td - 1; _++)
        base_zpe = modpow<INT, LINT>(base_zpe, pi, p);
      for (INT dn = 0;; dn += m) {
        assert(dn < p);
        if (memo.find(base_zpe) != memo.end()) {
          bsgs = dn + memo[base_zpe];
          break;
        }
        base_zpe = LINT(base_zpe) * offset % p;
      }
    }

    z = LINT(z) * modpow<INT, LINT>(vs, bsgs, p) % p;
    zpe = LINT(zpe) * modpow<INT, LINT>(vspe, bsgs, p) % p;
  }
  return z;
}

template <typename INT, typename LINT>
INT kth_root(INT a, INT k, INT p) {
  a %= p;
  if (k == 0) return a == 1 ? a : -1;
  if (a <= 1 || k <= 1) return a;
  INT g = gcd(p - 1, k);
  if (modpow<INT, LINT>(a, (p - 1) / g, p) != 1) return -1;
  if (LINT(g) * g <= p) {
    a = modpow<INT, LINT>(a, inv(k / g, (p - 1) / g), p);
    unordered_map<INT, int> fac;
    for (auto f : factorize(g)) fac[f]++;
    for (auto pp : fac) a = pe_root<INT, LINT>(a, pp.first, pp.second, p);
    return a;
  } else {
    // find primitive root
    auto pf_p = factorize(p - 1);
    vector<INT> fac;
    for (auto &f : pf_p) fac.push_back(f);
    fac.erase(unique(begin(fac), end(fac)), end(fac));
    auto ok = [&](INT pr) {
      for (auto &f : fac)
        if (modpow<INT, LINT>(pr, (p - 1) / f, p) == 1) return false;
      return true;
    };
    INT pr = 1;
    while (!ok(pr)) ++pr;
    // BS-GS ... find  {pr ^ g} ^ n = a mod p
    INT base = modpow<INT, LINT>(pr, g, p);
    INT m = sqrt((p - 1) / g) + 1;
    unordered_map<INT, INT> memo;
    for (INT i = 0, c = 1; i < m; ++i) {
      memo[c] = i;
      c = LINT(c) * base % p;
      if (c == 1) break;
    }
    INT n = -1, offset = modpow<INT, LINT>(inv(base, p), m, p);
    for (INT dn = 0, r = a;; dn += m) {
      assert(LINT(dn) * g <= p);
      if (memo.find(r) != memo.end()) {
        n = dn + memo[r];
        break;
      }
      r = LINT(r) * offset % p;
    }
    INT y = LINT(n) * inv(k / g, (p - 1) / g) % ((p - 1) / g);
    return modpow<INT, LINT>(pr, y, p);
  }
}

}  // namespace kth_root_mod
using kth_root_mod::kth_root;

int naive(int Y, int K, int P) {
  Y %= P;
  rep(x, P) {
    int n = inner::modpow<int, ll>(x, K, P);
    if (n == Y) return x;
  }
  return -1;
}

void solve() {
  ini(T);
  rep(_, T) {
    inl(p, k, a);
    ll ans = kth_root<int64_t, __int128_t>(a, k, p);
    out(ans);
  }
}
0