Submit Info #23368

Problem Lang User Status Time Memory
Kth Root(Mod) cpp Nyaan AC 45 ms 0.75 MiB

ケース詳細
Name Status Time Memory
Tonelli-Shanks_worstcase_00 AC 39 ms 0.65 MiB
Tonelli-Shanks_worstcase_01 AC 45 ms 0.65 MiB
Tonelli-Shanks_worstcase_02 AC 44 ms 0.67 MiB
Tonelli-Shanks_worstcase_03 AC 44 ms 0.73 MiB
Tonelli-Shanks_worstcase_04 AC 40 ms 0.67 MiB
example_00 AC 2 ms 0.67 MiB
max_random_00 AC 12 ms 0.67 MiB
max_random_01 AC 11 ms 0.74 MiB
max_random_02 AC 11 ms 0.67 MiB
max_random_03 AC 6 ms 0.75 MiB
max_random_04 AC 10 ms 0.74 MiB
random_00 AC 2 ms 0.67 MiB
random_01 AC 5 ms 0.67 MiB
random_02 AC 6 ms 0.61 MiB
random_03 AC 3 ms 0.67 MiB
random_04 AC 3 ms 0.66 MiB
safe_prime_00 AC 7 ms 0.67 MiB
safe_prime_01 AC 9 ms 0.65 MiB
safe_prime_02 AC 8 ms 0.66 MiB
safe_prime_03 AC 7 ms 0.71 MiB
safe_prime_04 AC 7 ms 0.67 MiB
small_00 AC 3 ms 0.67 MiB

#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 { 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 & 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 & 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 & 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; 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; unordered_map<decltype(mint::a), INT> memo; INT m = sqrt(pi); memo.reserve(m); mint offset; { mint base = vspe; for (INT _ = 0; _ < t - ei - 1; _++) base = base.pow(pi); offset = base.inverse().pow(m); mint cvs = one; for (INT i = 0; i < m; i++) { memo[cvs.get()] = i; cvs *= base; if (cvs == one) break; } } 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 // memo[n] = vs ^ n ^ ( p_i ^ (td - 1) ) INT bsgs = -1; { mint base_zpe = zpe.inverse(); for (INT _ = 0; _ < td - 1; _++) base_zpe = base_zpe.pow(pi); for (INT dn = 0;; dn += m) { assert(dn < p); if (memo.find(base_zpe.get()) != memo.end()) { bsgs = dn + memo[base_zpe.get()]; break; } base_zpe *= offset; } } 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; unordered_map<decltype(mint::a), INT> memo; mint c = one; for (INT i = 0; i < m; ++i) { memo[c.get()] = i; c *= base; if (c == one) break; } INT n = -1; mint offset = base.inverse().pow(m), r = a; for (INT dn = 0;; dn += m) { if (memo.find(r.get()) != memo.end()) { n = dn + memo[r.get()]; break; } r *= offset; } 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(K, Y, P); int ans = kth_root(Y, K, P); out(ans); } }