結果
問題 | No.981 一般冪乗根 |
ユーザー | Pachicobue |
提出日時 | 2023-08-14 09:12:15 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 9 ms / 6,000 ms |
コード長 | 21,963 bytes |
コンパイル時間 | 4,115 ms |
コンパイル使用メモリ | 302,348 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-05-01 21:49:02 |
合計ジャッジ時間 | 58,913 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
6,816 KB |
testcase_01 | AC | 4 ms
6,944 KB |
testcase_02 | AC | 4 ms
6,940 KB |
testcase_03 | AC | 4 ms
6,944 KB |
testcase_04 | AC | 3 ms
6,944 KB |
testcase_05 | AC | 3 ms
6,944 KB |
testcase_06 | AC | 4 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 3 ms
6,940 KB |
testcase_09 | AC | 4 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,940 KB |
testcase_13 | AC | 4 ms
6,940 KB |
testcase_14 | AC | 3 ms
6,944 KB |
testcase_15 | AC | 3 ms
6,940 KB |
testcase_16 | AC | 3 ms
6,940 KB |
testcase_17 | AC | 3 ms
6,948 KB |
testcase_18 | AC | 3 ms
6,940 KB |
testcase_19 | AC | 3 ms
6,940 KB |
testcase_20 | AC | 3 ms
6,940 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 | 3 ms
6,944 KB |
testcase_28 | AC | 9 ms
6,940 KB |
evil_60bit1.txt | AC | 10 ms
6,940 KB |
evil_60bit2.txt | AC | 11 ms
6,948 KB |
evil_60bit3.txt | AC | 10 ms
6,940 KB |
evil_hack | AC | 2 ms
6,940 KB |
evil_hard_random | AC | 9 ms
6,940 KB |
evil_hard_safeprime.txt | AC | 12 ms
6,944 KB |
evil_hard_tonelli0 | AC | 9 ms
6,944 KB |
evil_hard_tonelli1 | AC | 3,616 ms
6,940 KB |
evil_hard_tonelli2 | AC | 120 ms
6,940 KB |
evil_hard_tonelli3 | AC | 373 ms
6,940 KB |
evil_sefeprime1.txt | AC | 13 ms
6,944 KB |
evil_sefeprime2.txt | AC | 13 ms
6,944 KB |
evil_sefeprime3.txt | AC | 12 ms
6,940 KB |
evil_tonelli1.txt | AC | 5,409 ms
6,940 KB |
evil_tonelli2.txt | AC | 5,392 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; using f64 = double; using f80 = long double; using f128 = __float128; constexpr i32 operator"" _i32(u64 v) { return v; } constexpr u32 operator"" _u32(u64 v) { return v; } constexpr i64 operator"" _i64(u64 v) { return v; } constexpr u64 operator"" _u64(u64 v) { return v; } constexpr f64 operator"" _f64(f80 v) { return v; } constexpr f80 operator"" _f80(f80 v) { return v; } using Istream = std::istream; using Ostream = std::ostream; using Str = std::string; template<typename T> using Lt = std::less<T>; template<typename T> using Gt = std::greater<T>; template<int n> using BSet = std::bitset<n>; template<typename T1, typename T2> using Pair = std::pair<T1, T2>; template<typename... Ts> using Tup = std::tuple<Ts...>; template<typename T, int N> using Arr = std::array<T, N>; template<typename... Ts> using Deq = std::deque<Ts...>; template<typename... Ts> using Set = std::set<Ts...>; template<typename... Ts> using MSet = std::multiset<Ts...>; template<typename... Ts> using USet = std::unordered_set<Ts...>; template<typename... Ts> using UMSet = std::unordered_multiset<Ts...>; template<typename... Ts> using Map = std::map<Ts...>; template<typename... Ts> using MMap = std::multimap<Ts...>; template<typename... Ts> using UMap = std::unordered_map<Ts...>; template<typename... Ts> using UMMap = std::unordered_multimap<Ts...>; template<typename... Ts> using Vec = std::vector<Ts...>; template<typename... Ts> using Stack = std::stack<Ts...>; template<typename... Ts> using Queue = std::queue<Ts...>; template<typename T> using MaxHeap = std::priority_queue<T>; template<typename T> using MinHeap = std::priority_queue<T, Vec<T>, Gt<T>>; template<typename T> using Opt = std::optional<T>; constexpr bool LOCAL = false; template<typename T> static constexpr T OjLocal(T oj, T local) { return LOCAL ? local : oj; } template<typename T> constexpr T LIMMIN = std::numeric_limits<T>::min(); template<typename T> constexpr T LIMMAX = std::numeric_limits<T>::max(); template<typename T> constexpr T INF = (LIMMAX<T> - 1) / 2; template<typename T = i64> constexpr T TEN(int N) { return N == 0 ? T{1} : TEN<T>(N - 1) * T{10}; } constexpr auto ABS(auto x) { return (x >= 0 ? x : -x); } auto makePair(const auto& x1, const auto& x2) { return std::make_pair(x1, x2); } auto makeTup(const auto&... xs) { return std::make_tuple(xs...); } template<typename T> constexpr bool chmin(T& x, const T& y, auto comp = Lt<T>{}) { return (comp(y, x) ? (x = y, true) : false); } template<typename T> constexpr bool chmax(T& x, const T& y, auto comp = Lt<T>{}) { return (comp(x, y) ? (x = y, true) : false); } constexpr i64 floorDiv(i64 x, i64 y) { assert(y != 0); if (y < 0) { x = -x, y = -y; } return x >= 0 ? x / y : (x - y + 1) / y; } constexpr i64 ceilDiv(i64 x, i64 y) { assert(y != 0); if (y < 0) { x = -x, y = -y; } return x >= 0 ? (x + y - 1) / y : x / y; } template<typename T> constexpr T powerSemiGroup(const T& x, i64 N, auto mul) { assert(N > 0); if (N == 1) { return x; } return (N % 2 == 1 ? mul(x, powerSemiGroup(x, N - 1, mul)) : powerSemiGroup(mul(x, x), N / 2, mul)); } template<typename T> constexpr auto powerSemiGroup(const auto& v, i64 N) { return powerSemiGroup(v, N, std::multiplies<T>{}); } template<typename T> constexpr T powerMonoid(const T& x, i64 N, const T& e, auto mul) { assert(N >= 0); return (N == 0 ? e : powerSemiGroup(x, N, mul)); } template<typename T> constexpr T powerMonoid(T x, i64 N, const T& e) { return powerMonoid(x, N, e, std::multiplies<T>{}); } template<typename T> constexpr T powerInt(T x, i64 N) { return powerMonoid(x, N, T{1}); } constexpr u64 powerMod(u64 x, i64 N, u64 mod) { assert(0 < mod); return powerMonoid(x, N, u64{1}, [&](u64 x, u64 y) { if (mod <= (u64)LIMMAX<u32>) { return x * y % mod; } else { return (u64)((u128)x * y % mod); } }); } constexpr auto sumAll(const auto& xs) { return std::accumulate(std::begin(xs), std::end(xs), decltype(xs[0]){}); } constexpr int lbInd(const auto& xs, const auto& x) { return std::ranges::lower_bound(xs, x) - std::begin(xs); } constexpr int ubInd(const auto& xs, const auto& x) { return std::ranges::upper_bound(xs, x) - std::begin(xs); } constexpr int find(const auto& xs, const auto& x) { const int i = lbInd(xs, x); if (i < std::ssize(xs) and xs[i] == x) { return i; } return std::ssize(xs); } constexpr void concat(auto& xs1, const auto& xs2) { std::ranges::copy(xs2, std::back_inserter(xs1)); } constexpr auto concatCopy(const auto& xs1, const auto& xs2) { auto Ans = xs1; return concat(Ans, xs2), Ans; } template<typename Ts, typename T> constexpr void fillAll(Ts& arr, const T& x) { if constexpr (std::is_convertible<T, Ts>::value) { arr = x; } else { for (auto& subarr : arr) { fillAll(subarr, x); } } } template<typename T> constexpr Vec<T> genVec(int N, auto gen) { Vec<T> ans; std::ranges::generate_n(std::back_inserter(ans), N, gen); return ans; } constexpr auto minAll(const auto& xs, auto... args) { return std::ranges::min(xs, args...); } constexpr auto maxAll(const auto& xs, auto... args) { return std::ranges::max(xs, args...); } constexpr int minInd(const auto& xs, auto... args) { return std::ranges::min_element(xs, args...) - std::begin(xs); } constexpr int maxInd(const auto& xs, auto... args) { return std::ranges::max_element(xs, args...) - std::begin(xs); } template<typename T = int> constexpr Vec<T> iotaVec(int N, T offset = 0) { Vec<T> ans(N); std::iota(std::begin(ans), std::end(ans), offset); return ans; } constexpr void plusAll(auto& xs, const auto& x) { std::ranges::for_each(xs, [&](auto& e) { e += x; }); } constexpr void reverseAll(auto& xs) { std::ranges::reverse(xs); } constexpr void sortAll(auto& xs, auto... args) { std::ranges::sort(xs, args...); } constexpr auto runLengthEncode(const auto& xs) { using T = typename std::decay<decltype(xs[0])>::type; Vec<Pair<T, int>> Ans; auto [l, px] = makePair(0, T{}); for (const T& x : xs) { if (l == 0 or x != px) { if (l > 0) { Ans.push_back({px, l}); } l = 1, px = x; } else { l++; } } if (l > 0) { Ans.push_back({px, l}); } return Ans; } inline Ostream& operator<<(Ostream& os, u128 v) { Str ans; if (v == 0) { ans = "0"; } while (v) { ans.push_back('0' + v % 10), v /= 10; } std::reverse(ans.begin(), ans.end()); return os << ans; } inline Ostream& operator<<(Ostream& os, i128 v) { bool minus = false; if (v < 0) { minus = true, v = -v; } return os << (minus ? "-" : "") << (u128)v; } constexpr bool isBitOn(u64 x, int i) { return assert(0 <= i and i < 64), ((x >> i) & 1_u64); } constexpr bool isBitOff(u64 x, int i) { return assert(0 <= i and i < 64), (not isBitOn(x, i)); } constexpr u64 bitMask(int w) { return assert(0 <= w and w <= 64), (w == 64 ? ~0_u64 : (1_u64 << w) - 1); } constexpr u64 bitMask(int s, int e) { return assert(0 <= s and s <= e and e <= 64), (bitMask(e - s) << s); } constexpr int floorLog2(u64 x) { return 63 - std::countl_zero(x); } constexpr int ceilLog2(u64 x) { return x == 0 ? -1 : std::bit_width(x - 1); } constexpr int order2(u64 x) { return std::countr_zero(x); } template<typename F> struct Fix : F { constexpr Fix(F&& f) : F{std::forward<F>(f)} {} template<typename... Args> constexpr auto operator()(Args&&... args) const { return F::operator()(*this, std::forward<Args>(args)...); } }; class irange { private: struct itr { constexpr itr(i64 start, i64 end, i64 step) : m_cnt{start}, m_step{step}, m_end{end}, m_inc{start <= end} {} constexpr bool operator!=(const itr&) const { return (m_inc ? m_cnt < m_end : m_end < m_cnt); } constexpr i64 operator*() { return m_cnt; } constexpr itr& operator++() { return m_cnt += m_step, *this; } i64 m_cnt, m_step, m_end; bool m_inc; }; i64 m_start, m_end, m_step; public: constexpr irange(i64 start, i64 end, i64 step = 1) : m_start{start}, m_end{end}, m_step{step} { assert(step != 0); } constexpr itr begin() const { return itr{m_start, m_end, m_step}; } constexpr itr end() const { return itr{m_start, m_end, m_step}; } }; constexpr irange rep(i64 end) { return irange(0, end, 1); } constexpr irange per(i64 rend) { return irange(rend - 1, -1, -1); } constexpr Pair<i64, i64> extgcd(i64 a, i64 b) { assert(a != 0 or b != 0); const i64 A = ABS(a), B = ABS(b); auto [x, y, g] = Fix([&](auto self, i64 a, i64 b) -> Tup<i64, i64, i64> { assert(0 <= a and a < b); if (a == 0) { return {0, 1, b}; } const auto [px, py, pg] = self(b % a, a); return {py - (b / a) * px, px, pg}; })(std::ranges::min(A, B), std::ranges::max(A, B)); if (A > B) { std::swap(x, y); } if (a < 0) { x = -x; } if (b < 0) { y = -y; } if (x < 0) { x += B / g, y -= (b > 0 ? a / g : -a / g); } return {x, y}; } constexpr i64 inverseMod(i64 a, i64 mod) { assert(mod > 0 and a % mod != 0); return extgcd(a % mod, mod).first; } constexpr i64 binSearch(i64 ng, i64 ok, auto check) { while (ABS(ok - ng) > 1) { const i64 mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; } constexpr f80 binSearch(f80 ng, f80 ok, auto check, int times) { for (auto _temp_name_0 [[maybe_unused]] : rep(times)) { const f80 mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; } constexpr u64 intNthRoot(u64 A, int K) { assert(K > 0); if (A == 0) { return 0; } if (K == 1) { return A; } if (K > 64) { return 1; } return binSearch(1_i64 << 32, 1_i64, [&](i64 a) { u64 x = (u64)1; for (auto _temp_name_1 [[maybe_unused]] : rep(K)) { if (x > A / a) { return false; } x *= a; } return true; }); } constexpr u64 intSqrt(u64 A) { return intNthRoot(A, 2); } template<typename Engine> class RNG { public: using result_type = typename Engine::result_type; using U = result_type; static constexpr U min() { return Engine::min(); } static constexpr U max() { return Engine::max(); } RNG() : RNG(std::random_device{}()) {} RNG(U seed) : m_rng(seed) {} U operator()() { return m_rng(); } template<typename T> requires std::is_integral_v<T> T val(T min, T max) { return std::uniform_int_distribution<T>(min, max)(m_rng); } template<typename T> Vec<T> vec(int N, T min, T max) { return genVec<T>(N, [&]() { return val<T>(min, max); }); } private: Engine m_rng; }; inline RNG<std::mt19937> rng; inline RNG<std::mt19937_64> rng64; constexpr u64 primitiveRoot(u64 P) { assert(P >= 2); Vec<u64> ps; { u64 Q = P - 1; for (u64 p = 2; p * p <= P - 1; p++) { if (Q % p == 0) { ps.push_back(p); } while (Q % p == 0) { Q /= p; } } if (Q > 1) { ps.push_back(Q); } } for (u64 r = 1; r < P; r++) { bool ok = true; for (u64 p : ps) { const u64 Q = powerMod(r, (P - 1) / p, P); if (Q == 1) { ok = false; break; } } if (ok) { return r; } } return 0; } template<u64 Mod, bool dynamic = false> requires(dynamic or (0 < Mod and Mod <= (u64)LIMMAX<i64>)) class modint { public: static constexpr bool isDynamic() { return dynamic; } static constexpr u64 mod() { if constexpr (dynamic) { return modRef(); } else { return Mod; } } static constexpr void setMod(u64 m) requires dynamic { assert(0 < m and m <= LIMMAX<i64>), modRef() = m; } constexpr modint() : m_val{0} {} constexpr modint(i64 v) : m_val{normll(v)} {} constexpr friend modint operator-(const modint& m) { return modint{0} - m; } constexpr friend modint& operator+=(modint& m1, const modint& m2) { return m1.m_val = norm(m1.m_val + m2.m_val), m1; } constexpr friend modint& operator-=(modint& m1, const modint& m2) { return m1.m_val = norm(m1.m_val + mod() - m2.m_val), m1; } constexpr friend modint& operator*=(modint& m1, const modint& m2) { if constexpr (dynamic) { if (mod() <= (u64)LIMMAX<u32>) { return (m1.m_val *= m2.m_val) %= mod(), m1; } else { return m1.m_val = (u64)((u128)m1.m_val * (u128)m2.m_val % (u128)mod()), m1; } } else { if constexpr (Mod <= (u64)LIMMAX<u32>) { return (m1.m_val *= m2.m_val) %= mod(), m1; } else { return m1.m_val = (u64)((u128)m1.m_val * (u128)m2.m_val % (u128)mod()), m1; } } } constexpr friend modint& operator/=(modint& m1, const modint& m2) { return m1 *= m2.inv(); } constexpr friend modint operator+(const modint& m1, const modint& m2) { auto ans = m1; return ans += m2; } constexpr friend modint operator-(const modint& m1, const modint& m2) { auto ans = m1; return ans -= m2; } constexpr friend modint operator*(const modint& m1, const modint& m2) { auto ans = m1; return ans *= m2; } constexpr friend modint operator/(const modint& m1, const modint& m2) { auto ans = m1; return ans /= m2; } constexpr friend bool operator==(const modint& m1, const modint& m2) { return m1.m_val == m2.m_val; } friend Istream& operator>>(Istream& is, modint& m) { i64 v; return is >> v, m = v, is; } friend Ostream& operator<<(Ostream& os, const modint& m) { return os << m.m_val; } constexpr u64 val() const { return m_val; } constexpr modint pow(i64 n) const { return powerInt(*this, n); } constexpr modint inv() const { return inverseMod(m_val, mod()); } private: static u64& modRef() requires dynamic { static u64 mod_ = 0; return mod_; } static constexpr u64 norm(u64 x) { return x < mod() ? x : x - mod(); } static constexpr u64 normll(i64 x) { x %= mod(); return norm(u64(x < 0 ? x + (i64)mod() : x)); } u64 m_val; }; using modint_1000000007 = modint<1000000007, false>; using modint_998244353 = modint<998244353, false>; template<u64 id> requires(id < (u64)LIMMAX<i64>) using modint_dynamic = modint<id, true>; template<u64 id> requires(id < (u64)LIMMAX<i64>) using modint_dynamic_reserved = modint<id | (1_u64 << 63), true>; constexpr bool millerRabin(u64 X, const Vec<u64>& as) { using mint = modint_dynamic_reserved<81165>; mint::setMod(X); const u64 d = (X - 1) >> order2(X - 1); for (u64 a : as) { if (X <= a) { break; } u64 s = d; mint x = mint(a).pow(s); while (x != 1 and x != X - 1 and s != X - 1) { s *= 2, x *= x; } if (x != X - 1 and s % 2 == 0) { return false; } } return true; } constexpr bool isPrime(u64 X) { if (X == 1) { return false; } if (X % 2 == 0) { return X == 2; } if (X < 4759123141_u64) { return millerRabin(X, {2_u64, 7_u64, 61_u64}); } else { return millerRabin(X, {2_u64, 325_u64, 9375_u64, 28178_u64, 450775_u64, 9780504_u64, 1795265022_u64}); } } constexpr u64 pollardRho(u64 X) { assert(1 <= X and X <= (u64)LIMMAX<i64>); if (X % 2 == 0) { return 2; } if (X == 1 or isPrime(X)) { return X; } using mint = modint_dynamic_reserved<77726>; mint::setMod(X); auto f = [&](mint x, mint c) { return x * x + c; }; const u64 gcdBlock = intNthRoot(X, 8); while (true) { const u64 a = rng64.val<u64>(0, X - 1); const mint c = rng64.val(2_u64, X - 1); mint x = a, y = a, sx = x, sy = y; mint p = 1; u64 g = 1; while (g == 1) { sx = x, sy = y; for (auto _temp_name_2 [[maybe_unused]] : rep(gcdBlock)) { x = f(x, c), y = f(f(y, c), c), p *= (x - y); } g = std::gcd(X, p.val()); } if (g == X) { x = sx, y = sy, g = 1; while (g == 1) { x = f(x, c), y = f(f(y, c), c), g = std::gcd(X, (x - y).val()); } } if (g != X) { return g; } } return X; } constexpr Vec<Pair<u64, int>> primeFactors(u64 X) { Vec<u64> Ans; Fix([&](auto dfs, u64 x) -> void { while (x % 2 == 0) { x /= 2, Ans.push_back(2); } if (x == 1) { return; } const u64 d = pollardRho(x); if (d == x) { return Ans.push_back(d), void(); } dfs(d), dfs(x / d); })(X); sortAll(Ans); return runLengthEncode(Ans); } constexpr Vec<u64> divisors(const Vec<Pair<u64, int>>& factors) { Vec<u64> Ans{1}; for (const auto& [p, e] : factors) { const int dn = (int)Ans.size(); u64 pe = p; for (auto _temp_name_3 [[maybe_unused]] : rep(e)) { for (int j : rep(dn)) { Ans.push_back(Ans[j] * pe); } pe *= p; } } return sortAll(Ans), Ans; } template<typename mint> Opt<mint> modNthRoot(mint A, i64 K) { constexpr auto Null = std::nullopt; const i64 P = mint::mod(); if (K == 0) { return A == 1 ? Opt<mint>{1_i64} : Opt<mint>{Null}; } if (A == 0 or A == 1) { return A; } const i64 g = std::gcd(P - 1, K); if (A.pow((P - 1) / g) != 1) { return Null; } A = A.pow(inverseMod(K / g, (P - 1) / g)); if (g == 1) { return A; } Vec<Tup<i64, int, int>> factors; { i64 Q = P - 1; for (const auto& [p, a] : primeFactors(g)) { int b = 0; while (Q % p == 0) { Q /= p, b++; } factors.push_back({p, a, b}); } } for (const auto& [p, a, b] : factors) { const i64 pa = powerInt(p, a), pb = powerInt(p, b); const i64 Q = (P - 1) / pb; mint X = (Q == 1 ? mint{1} : A.pow(inverseMod(pa, Q))); if (a == b) { A = X; continue; } auto ordLog_p = [&](mint X) { for (int i : per(b + 1)) { if (X == 1) { return i; } X = X.pow(p); } return 0; }; auto trunc = [&](mint X, int ord) { assert(ord < b); for (auto _temp_name_4 [[maybe_unused]] : rep((b - 1) - ord)) { X = X.pow(p); } return X; }; mint Eraser = 1; for (mint Z = 2;; Z += 1) { Eraser = Z.pow(Q); if (ordLog_p(Eraser) == 0) { break; } } Vec<mint> pErasers(b, Eraser); for (int i : rep(b - 1)) { pErasers[i + 1] = pErasers[i].pow(p); } assert(pErasers[b - 1].pow(p) == 1); const mint ipEraser = pErasers[b - 1].inv(); const i64 M = std::max(1_i64, (i64)intSqrt(p * (b - a) / 4)), W = ceilDiv((p - 1), M); Map<u64, i64> Memo; for (mint E = 1, ER = pErasers[b - 1].pow(W); i64 x : rep(M)) { Memo[E.val()] = W * x, E *= ER; } auto logErase = [&](mint X) { for (i64 i : rep(W + 1)) { if (Memo.count(X.val()) > 0) { return Memo[X.val()] + i; } X *= ipEraser; } return -1_i64; }; mint Error = (X.pow(pa) / A); while (true) { const int o = ordLog_p(Error); assert(o >= a); if (o == b) { break; } const i64 e = logErase(trunc(Error, o)); assert(e != -1); X *= pErasers[o - a].pow(p - e), Error *= pErasers[o].pow(p - e); } A = X; } return A; } class Printer { public: Printer(Ostream& os = std::cout) : m_os{os} { m_os << std::fixed << std::setprecision(15); } int operator()(const auto&... args) { return dump(args...), 0; } int ln(const auto&... args) { return dump(args...), m_os << '\n', 0; } int el(const auto&... args) { return dump(args...), m_os << std::endl, 0; } private: void dump(const auto& v) { m_os << v; } int dump(const auto& v, const auto&... args) { return dump(v), m_os << ' ', dump(args...), 0; } template<typename... Args> void dump(const Vec<Args...>& vs) { for (Str delim = ""; const auto& v : vs) { m_os << std::exchange(delim, " "), dump(v); } } Ostream& m_os; }; inline Printer out; class Scanner { public: Scanner(Istream& is = std::cin) : m_is{is} { m_is.tie(nullptr)->sync_with_stdio(false); } template<typename T> T val() { T v; return m_is >> v, v; } template<typename T> T val(T offset) { return val<T>() - offset; } template<typename T> Vec<T> vec(int N) { return genVec<T>(N, [&]() { return val<T>(); }); } template<typename T> Vec<T> vec(int N, T offset) { return genVec<T>(N, [&]() { return val<T>(offset); }); } template<typename T> Vec<Vec<T>> vvec(int n, int m) { return genVec<Vec<T>>(n, [&]() { return vec<T>(m); }); } template<typename T> Vec<Vec<T>> vvec(int n, int m, const T offset) { return genVec<Vec<T>>(n, [&]() { return vec<T>(m, offset); }); } template<typename... Args> auto tup() { return Tup<Args...>{val<Args>()...}; } template<typename... Args> auto tup(Args... offsets) { return Tup<Args...>{val<Args>(offsets)...}; } private: Istream& m_is; }; inline Scanner in; int main() { const int T = in.val<int>(); using mint = modint_dynamic<0>; for (auto _temp_name_5 [[maybe_unused]] : rep(T)) { const auto [P, K, Y] = in.tup<u64, i64, i64>(); mint::setMod(P); const auto ans = modNthRoot(mint(Y), K); if (ans) { out.ln(ans.value()); } else { out.ln(-1); } } return 0; }