#555807 (C++17) No.981 一般冪乗根

提出ソース
結果

問題	No.981 一般冪乗根
ユーザー	NyaanNyaan
提出日時	2020-09-19 17:02:19
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	4 ms / 6,000 ms
コード長	19,332 bytes
コンパイル時間	4,559 ms
コンパイル使用メモリ	340,744 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-06-23 17:56:45
合計ジャッジ時間	50,546 ms
ジャッジサーバーID （参考情報）	judge1 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 6,812 KB
testcase_01	AC	4 ms 6,816 KB
testcase_02	AC	3 ms 6,940 KB
testcase_03	AC	3 ms 6,940 KB
testcase_04	AC	4 ms 6,940 KB
testcase_05	AC	3 ms 6,940 KB
testcase_06	AC	3 ms 6,940 KB
testcase_07	AC	3 ms 6,940 KB
testcase_08	AC	3 ms 6,944 KB
testcase_09	AC	3 ms 6,940 KB
testcase_10	AC	3 ms 6,940 KB
testcase_11	AC	3 ms 6,944 KB
testcase_12	AC	3 ms 6,944 KB
testcase_13	AC	3 ms 6,944 KB
testcase_14	AC	3 ms 6,944 KB
testcase_15	AC	3 ms 6,940 KB
testcase_16	AC	3 ms 6,944 KB
testcase_17	AC	3 ms 6,944 KB
testcase_18	AC	3 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,944 KB
testcase_22	AC	3 ms 6,944 KB
testcase_23	AC	3 ms 6,944 KB
testcase_24	AC	3 ms 6,940 KB
testcase_25	AC	4 ms 6,944 KB
testcase_26	AC	4 ms 6,940 KB
testcase_27	AC	2 ms 6,940 KB
testcase_28	AC	4 ms 6,940 KB
evil_60bit1.txt	AC	7 ms 6,940 KB
evil_60bit2.txt	AC	7 ms 6,944 KB
evil_60bit3.txt	AC	7 ms 6,944 KB
evil_hack	AC	2 ms 6,940 KB
evil_hard_random	AC	7 ms 6,940 KB
evil_hard_safeprime.txt	AC	8 ms 6,940 KB
evil_hard_tonelli0	AC	4 ms 6,944 KB
evil_hard_tonelli1	AC	313 ms 6,940 KB
evil_hard_tonelli2	AC	21 ms 6,940 KB
evil_hard_tonelli3	AC	51 ms 6,940 KB
evil_sefeprime1.txt	AC	8 ms 6,944 KB
evil_sefeprime2.txt	AC	8 ms 6,940 KB
evil_sefeprime3.txt	AC	8 ms 6,940 KB
evil_tonelli1.txt	AC	416 ms 6,944 KB
evil_tonelli2.txt	AC	412 ms 6,940 KB
権限があれば一括ダウンロードができます
ソースコード

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

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;

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

// fast BS-GS
template <typename T>
struct Memo {
  Memo(const T &g, int s, int period)
      : size(1 << __lg(min(s, period))),
        mask(size - 1),
        period(period),
        vs(size),
        os(size + 1) {
    T x(1);
    for (int i = 0; i < size; ++i, x *= g) os[x.get() & mask]++;
    for (int i = 1; i < size; ++i) os[i] += os[i - 1];
    x = 1;
    for (int i = 0; i < size; ++i, x *= g) vs[--os[x.get() & mask]] = {x, i};
    gpow = x;
    os[size] = size;
  }
  int find(T x) const {
    for (int t = 0; t < period; t += size, x *= gpow) {
      for (int m = (x.get() & mask), i = os[m]; i < os[m + 1]; ++i) {
        if (x == vs[i].first) {
          int ret = vs[i].second - t;
          return ret < 0 ? ret + period : ret;
        }
      }
    }
    assert(0);
  }
  T gpow;
  int size, mask, period;
  vector<pair<T, int> > vs;
  vector<int> os;
};

using inner::gcd;
using inner::inv;
using inner::modpow;
template <typename INT, typename LINT, typename mint>
mint pe_root(INT c, INT pi, INT ei, INT p) {
  if (mint::get_mod() != decltype(mint::a)(p)) mint::set_mod(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);
  mint mc = c, one = 1;
  mint z = mc.pow((s * u + 1) / pe);
  mint zpe = mc.pow(s * u);
  if (zpe == one) return z;

  assert(t > ei);
  mint vs;
  {
    INT ptm1 = 1;
    for (INT _ = 0; _ < t - 1; ++_) ptm1 *= pi;
    for (mint v = 2;; v += one) {
      vs = v.pow(s);
      if (vs.pow(ptm1) != one) break;
    }
  }

  mint vspe = vs.pow(pe);
  INT vs_e = ei;
  mint base = vspe;
  for (INT _ = 0; _ < t - ei - 1; _++) base = base.pow(pi);
  Memo<mint> memo(base, (INT)(sqrt(t - ei) * sqrt(pi)) + 1, pi);

  while (zpe != one) {
    mint tmp = zpe;
    INT td = 0;
    while (tmp != 1) ++td, tmp = tmp.pow(pi);
    INT e = t - td;
    while (vs_e != e) {
      vs = vs.pow(pi);
      vspe = vspe.pow(pi);
      ++vs_e;
    }

    // BS-GS ... find (zpe * ( vspe ^ n ) ) ^( p_i ^ (td - 1) ) = 1
    mint base_zpe = zpe.inverse();
    for (INT _ = 0; _ < td - 1; _++) base_zpe = base_zpe.pow(pi);
    INT bsgs = memo.find(base_zpe);

    z *= vs.pow(bsgs);
    zpe *= vspe.pow(bsgs);
  }
  return z;
}

template <typename INT, typename LINT, typename mint>
INT inner_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;

  assert(p > 2);
  if (mint::get_mod() != decltype(mint::a)(p)) mint::set_mod(p);
  INT g = gcd(p - 1, k);
  if (modpow<INT, LINT>(a, (p - 1) / g, p) != 1) return -1;
  if (LINT(g) * g <= p) {
    a = mint(a).pow(inv(k / g, (p - 1) / g)).get();
    unordered_map<INT, int> fac;
    for (auto &f : factorize(g)) fac[f]++;
    if (mint::get_mod() != decltype(mint::a)(p)) mint::set_mod(p);
    for (auto pp : fac)
      a = pe_root<INT, LINT, mint>(a, pp.first, pp.second, p).get();
    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));
    if (mint::get_mod() != decltype(mint::a)(p)) mint::set_mod(p);
    mint one = 1, pr = 1;
    auto ok = [&]() {
      for (auto &f : fac)
        if (pr.pow((p - 1) / f) == one) return false;
      return true;
    };
    while (!ok()) pr += one;

    // BS-GS ... find  {pr ^ g} ^ n = a mod p
    mint base = pr.pow(g);
    INT m = sqrt((p - 1) / g) + 1;
    Memo<mint> memo(base, m, (p - 1) / g);
    INT n = memo.find(mint(a));

    INT y = LINT(n) * inv(k / g, (p - 1) / g) % ((p - 1) / g);
    return pr.pow(y).get();
  }
}

int64_t kth_root(int64_t a, int64_t k, int64_t p) {
  if (max({a, k, p}) < (1LL << 30))
    return inner_kth_root<int32_t, int64_t, ArbitraryLazyMontgomeryModInt>(a, k,
                                                                           p);
  else
    return inner_kth_root<int64_t, __int128_t, montgomery64>(a, k, p);
}

}  // namespace kth_root_mod
using kth_root_mod::kth_root;

void solve() {
  ini(T);
  rep(_, T) {
    inl(p, k, a);
    ll ans = kth_root(a, k, p);
    out(ans);
  }
}
yukicoder

結果

テストケース

ソースコード
