結果
| 問題 |
No.981 一般冪乗根
|
| ユーザー |
 hashiryo
|
| 提出日時 | 2022-11-13 20:51:26 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 16,682 bytes |
| コンパイル時間 | 2,756 ms |
| コンパイル使用メモリ | 216,368 KB |
| 最終ジャッジ日時 | 2025-02-08 20:00:13 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 7 WA * 37 |
ソースコード
#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
constexpr std::uint64_t mul(std::uint64_t x, std::uint64_t y, std::uint64_t m) {
return (__uint128_t)x * y % m;
}
template <std::uint64_t... args>
constexpr bool miller_rabin(std::uint64_t n) {
const std::uint64_t s = __builtin_ctzll(n - 1), d = n >> s;
for (auto a : {args...}) {
std::uint64_t b = a % n, p = 1, i = s;
for (std::uint64_t k = d, x = b;; x = mul(x, x, n))
if (k & 1 ? p = mul(p, x, n) : 0; !(k >>= 1)) break;
while (p != 1 && p != n - 1 && b && i--) p = mul(p, p, n);
if (p != n - 1 && i != s) return false;
}
return true;
}
constexpr bool is_prime(std::uint64_t n) {
if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
if (n < UINT_MAX) return miller_rabin<2, 7, 61>(n);
return miller_rabin<2, 325, 9375, 28178, 450775, 9780504, 1795265022>(n);
}
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, std::size_t _Nm>
struct ConstexprArray {
constexpr std::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] = {};
std::size_t sz = 0;
};
class Factors
: public ConstexprArray<std::pair<std::uint64_t, std::uint16_t>, 16> {
static constexpr std::uint64_t rho(std::uint64_t n, std::uint64_t c) {
auto f = [n, c](std::uint64_t x) { return ((__uint128_t)x * x + c) % n; };
std::uint64_t x = 1, y = 2, z = 1, q = 1, g = 1;
const std::uint64_t m = 1LL << (std::__lg(n) / 5);
for (std::uint64_t r = 1, i = 0; g == 1; r <<= 1) {
for (x = y, i = r; i--;) y = f(y);
for (std::uint64_t k = 0; k < r && g == 1; g = std::gcd(q, n), k += m)
for (z = y, i = std::min(m, r - k); i--;)
y = f(y), q = mul(q, (x > y ? x - y : y - x), n);
}
if (g == n) do {
z = f(z), g = std::gcd((x > z ? x - z : z - x), n);
} while (g == 1);
return g;
}
static constexpr std::uint64_t find_prime_factor(std::uint64_t n) {
if (is_prime(n)) return n;
for (std::uint64_t i = 100, m = 0; i--; n = m)
if (m = rho(n, i + 1); is_prime(m)) return m;
return 0;
}
constexpr void init(std::uint64_t n) {
for (std::uint64_t 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 (std::uint64_t 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(std::uint64_t n) { init(n), bubble_sort(dat, dat + sz); }
};
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)); }
constexpr std::uint64_t primitive_root(std::uint64_t p) {
if (assert(is_prime(p)); p == 2) return 1;
auto f = Factors(p - 1);
for (std::uint64_t ret = 2, pw = 0, x = 0, k = 0, ng = 0;; ret++) {
for (auto [q, e] : f) {
for (pw = 1, x = ret, k = (p - 1) / q;; x = mul(x, x, p))
if (k & 1 ? pw = mul(pw, x, p) : 0; !(k >>= 1)) break;
if (ng = (pw == 1)) break;
}
if (!ng) return ret;
}
}
namespace modint_internal {
using namespace std;
struct modint_base {};
struct sta_mint_base : modint_base {};
struct dyn_mint_base : modint_base {};
template <class mod_t>
constexpr bool is_modint_v = is_base_of_v<modint_base, mod_t>;
template <class mod_t>
constexpr bool is_staticmodint_v = is_base_of_v<sta_mint_base, mod_t>;
template <class mod_t>
constexpr bool is_dynamicmodint_v = is_base_of_v<dyn_mint_base, mod_t>;
using u64 = uint64_t;
using u128 = __uint128_t;
template <class D>
struct ModIntImpl {
static constexpr inline auto modulo() { return D::mod; }
constexpr D operator-() const { return D() -= (D &)*this; }
constexpr D &operator/=(const D &r) { return (D &)*this *= r.inv(); }
constexpr D operator+(const D &r) const { return D((D &)*this) += r; }
constexpr D operator-(const D &r) const { return D((D &)*this) -= r; }
constexpr D operator*(const D &r) const { return D((D &)*this) *= r; }
constexpr D operator/(const D &r) const { return D((D &)*this) /= r; }
constexpr bool operator!=(const D &r) const { return !((D &)*this == r); }
constexpr D pow(u64 k) const {
for (D ret(1), b((const D &)*this);; b *= b)
if (k & 1 ? ret *= b : 0; !(k >>= 1)) return ret;
}
constexpr D inv() const {
typename D::Int x = 1, y = 0, a = ((D *)this)->val(), b = D::mod;
for (typename D::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), D(x);
}
constexpr bool operator<(const D &r) const {
return ((D *)this)->val() < r.val();
} // for set or map
friend ostream &operator<<(ostream &os, const D &r) { return os << r.val(); }
friend istream &operator>>(istream &is, D &r) {
long long v;
return is >> v, r = D(v), is;
}
};
template <class B>
struct ModInt_Na : public B, public ModIntImpl<ModInt_Na<B>> {
using Int = typename B::Int;
using DUint = conditional_t<is_same_v<typename B::Uint, uint32_t>, u64, u128>;
friend ModIntImpl<ModInt_Na<B>>;
constexpr ModInt_Na() = default;
template <class T, enable_if_t<is_modint_v<T>, nullptr_t> = nullptr>
constexpr ModInt_Na(T n) : ModInt_Na(n.val()) {}
template <class T,
enable_if_t<is_convertible_v<T, __int128_t>, nullptr_t> = nullptr>
constexpr ModInt_Na(T n) : x(n < 0 ? B::mod - ((-n) % B::mod) : n % B::mod) {}
#define ASSIGN(m, p) return x m## = B::mod & -((x p## = r.x) >= B::mod), *this
constexpr ModInt_Na &operator+=(const ModInt_Na &r) { ASSIGN(-, +); }
constexpr ModInt_Na &operator-=(const ModInt_Na &r) { ASSIGN(+, -); }
#undef ASSIGN
constexpr ModInt_Na &operator*=(const ModInt_Na &r) {
return x = (DUint)(x)*r.x % B::mod, *this;
}
constexpr bool operator==(const ModInt_Na &r) const { return x == r.x; }
constexpr auto val() const { return x; }
private:
typename B::Uint x = 0;
};
template <class B>
struct ModInt_Mon : public B, public ModIntImpl<ModInt_Mon<B>> {
using Int = int64_t;
using mod_t = ModInt_Mon;
friend ModIntImpl<ModInt_Mon<B>>;
constexpr ModInt_Mon() = default;
template <class T, enable_if_t<is_modint_v<T>, nullptr_t> = nullptr>
constexpr ModInt_Mon(T n) : ModInt_Mon(n.val()) {}
template <class T,
enable_if_t<is_convertible_v<T, __int128_t>, nullptr_t> = nullptr>
constexpr ModInt_Mon(T n)
: x(mul(n < 0 ? B::mod - ((-n) % B::mod) : n % B::mod, B::r2)) {}
#define ASGN(op, a) return x op## = a, x += (B::mod << 1) & -(x >> 63), *this
constexpr mod_t &operator+=(const mod_t &r) { ASGN(+, r.x - (B::mod << 1)); }
constexpr mod_t &operator-=(const mod_t &r) { ASGN(-, r.x); }
#undef ASGN
constexpr mod_t &operator*=(const mod_t &r) { return x = mul(x, r.x), *this; }
constexpr bool operator==(const mod_t &r) const { return norm() == r.norm(); }
constexpr u64 val() const {
u64 ret = reduce(x) - B::mod;
return ret + (B::mod & -(ret >> 63));
}
private:
static constexpr inline u64 reduce(const u128 &w) {
return u64(w >> 64) + B::mod - ((u128(u64(w) * B::iv) * B::mod) >> 64);
}
static constexpr inline u64 mul(u64 l, u64 r) { return reduce(u128(l) * r); }
u64 x = 0;
constexpr inline u64 norm() const { return x - (B::mod & -(x >= B::mod)); }
};
constexpr u64 mul_inv(u64 n, int e = 6, u64 x = 1) {
return e ? mul_inv(n, e - 1, x * (2 - x * n)) : x;
}
template <u64 MOD>
struct StaticB_Na : sta_mint_base {
protected:
using Int = conditional_t < MOD < INT_MAX, int32_t,
conditional_t<MOD<LLONG_MAX, int64_t, __int128_t>>;
using Uint = conditional_t < MOD < INT_MAX, uint32_t,
conditional_t<MOD<LLONG_MAX, u64, u128>>;
static constexpr Uint mod = MOD;
};
template <u64 MOD>
struct StaticB_Mon : sta_mint_base {
protected:
static_assert(MOD & 1);
static constexpr u64 mod = MOD, iv = mul_inv(mod), r2 = -u128(mod) % mod;
};
template <class I, int id = -1>
struct DynamicB_Na : dyn_mint_base {
static_assert(is_integral_v<I>);
static inline void set_mod(I m) { mod = m; }
protected:
using Int = I;
using Uint = make_unsigned_t<Int>;
static inline Uint mod;
};
template <int id>
struct DynamicB_Mon : dyn_mint_base {
static inline void set_mod(u64 m) {
assert(m & 1), iv = mul_inv(mod = m), r2 = -u128(m) % m;
}
protected:
static inline u64 mod, iv, r2;
};
template <u64 mod>
using StaticModInt =
conditional_t<mod &(INT_MAX <= mod) & (mod < LLONG_MAX),
ModInt_Mon<StaticB_Mon<mod>>, ModInt_Na<StaticB_Na<mod>>>;
struct Montgomery {};
template <class Int, int id = -1>
using DynamicModInt =
conditional_t<is_same_v<Int, Montgomery>, ModInt_Mon<DynamicB_Mon<id>>,
ModInt_Na<DynamicB_Na<Int, id>>>;
} // namespace modint_internal
using modint_internal::DynamicModInt, modint_internal::StaticModInt,
modint_internal::Montgomery, modint_internal::is_dynamicmodint_v,
modint_internal::is_modint_v, modint_internal::is_staticmodint_v;
template <class mod_t, std::size_t LIM>
mod_t get_inv(int n) {
static_assert(is_modint_v<mod_t>);
static const auto m = mod_t::modulo();
static mod_t dat[LIM];
static int l = 1;
if (l == 1) dat[l++] = 1;
while (l <= n) dat[l++] = dat[m % l] * (m - m / l);
return dat[n];
}
template <class Int>
inline Int inv_mod(Int a, Int mod) {
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;
}
template <class Int, class mod_t>
mod_t peth_root(mod_t c, Int pi, int ei) {
const Int p = mod_t::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 = inv_mod(pe - s % pe, pe);
mod_t ONE = 1, z = c.pow((s * u + 1) / pe), zpe = c.pow(s * u);
if (zpe == ONE) return z;
assert(t > ei);
Int ptm1 = 1;
for (int i = t; --i;) ptm1 *= pi;
mod_t vs, base;
for (mod_t v = 2;; v += ONE)
if (vs = v.pow(s), base = vs.pow(ptm1); base != ONE) break;
std::unordered_map<Int, Int> memo;
int m = sqrt(pi * (t - ei)) + 1;
mod_t x = 1, vspe = vs.pow(pe);
for (int i = 0; i < m; i++, x *= base) memo.insert({x.val(), i});
x = mod_t(1) / x;
for (int vs_e = ei, td; zpe != ONE;) {
mod_t tmp = zpe, base_zpe = mod_t(1) / zpe;
for (td = 0; tmp != ONE; td++) tmp = tmp.pow(pi);
for (int e = t - td; vs_e != e; vs_e++)
vs = vs.pow(pi), vspe = vspe.pow(pi);
for (int i = td; --i;) base_zpe = base_zpe.pow(pi);
for (Int i = 0, n;; base_zpe *= x, i++)
if (auto it = memo.find(base_zpe.val()); it != memo.end()) {
z *= vs.pow(n = i * m + it->second), zpe *= vspe.pow(n);
break;
}
}
return z;
}
template <class Int, class mod_t>
Int inner_kth_root(Int a, std::uint64_t k, Int p) {
if (k == 0) return a == 1 ? a : -1;
if (a <= 1 || k <= 1) return a;
assert(p > 2);
mod_t::set_mod(p);
Int g = std::gcd(k, p - 1);
mod_t ma = a;
Int pp = (p - 1) / g, kk = (k / g) % pp;
if (ma.pow(pp) != mod_t(1)) return -1;
ma = ma.pow(inv_mod(kk, pp));
for (auto [pi, ei] : Factors(g)) ma = peth_root(ma, pi, ei);
return ma.val();
}
std::int64_t kth_root(std::int64_t a, std::uint64_t k, std::int64_t p) {
if (a %= p; p < INT_MAX)
return inner_kth_root<int, DynamicModInt<int, -2>>(a, k, p);
else
return inner_kth_root<std::int64_t, DynamicModInt<Montgomery, -2>>(a, k, p);
}
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 << 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 << kth_root(a, k, p) << '\n';
}
return 0;
}
} // namespace yukicoder981
signed main() {
// yosupo_kth_root::main();
yukicoder981::main();
return 0;
}