結果
| 問題 |
No.981 一般冪乗根
|
| ユーザー |
 hashiryo
|
| 提出日時 | 2022-11-16 01:52:04 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 7 ms / 6,000 ms |
| コード長 | 13,661 bytes |
| コンパイル時間 | 2,802 ms |
| コンパイル使用メモリ | 214,896 KB |
| 最終ジャッジ日時 | 2025-02-08 20:37:08 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 44 |
コンパイルメッセージ
main.cpp: In function ‘Int math_internal::peth_root(Int, Int, int, const mod_pro_t&) [with Int = int; mod_pro_t = MIntPro_Na<unsigned int>]’:
main.cpp:227:23: warning: argument to variable-length array is too large [-Wvla-larger-than=]
227 | std::pair<Int, int> vec[size];
| ^~~
main.cpp:227:23: note: limit is 9223372036854775807 bytes, but argument is 18446744056529682432
main.cpp: In function ‘Int math_internal::peth_root(Int, Int, int, const mod_pro_t&) [with Int = long int; mod_pro_t = MIntPro_Montg]’:
main.cpp:227:23: warning: argument to variable-length array is too large [-Wvla-larger-than=]
227 | std::pair<Int, int> vec[size];
| ^~~
main.cpp:227:23: note: limit is 9223372036854775807 bytes, but argument is 18446744039349813248
ソースコード
#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
namespace math_internal {
using namespace std;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;
class MIntPro_Montg {
const u64 mod, iv, r2;
constexpr u64 inv(u64 n, int e = 6, u64 x = 1) {
return e ? inv(n, e - 1, x * (2 - x * n)) : x;
}
constexpr u64 reduce(const u128 &w) const {
return u64(w >> 64) + mod - ((u128(u64(w) * iv) * mod) >> 64);
}
public:
constexpr MIntPro_Montg(u64 m) : mod(m), iv(inv(m)), r2(-u128(mod) % mod) {}
constexpr u64 mul(u64 l, u64 r) const { return reduce(u128(l) * r); }
#define BOP(op, a) return l op## = a, l += (mod << 1) & -(l >> 63)
constexpr u64 plus(u64 l, u64 r) const { BOP(+, r - (mod << 1)); }
constexpr u64 diff(u64 l, u64 r) const { BOP(-, r); }
#undef BOP
constexpr u64 set(u64 n) const { return mul(n, r2); }
constexpr u64 get(u64 n) const {
u64 ret = reduce(n) - mod;
return ret + (mod & -(ret >> 63));
}
constexpr u64 norm(u64 n) const { return n - (mod & -(n >= mod)); }
constexpr u64 modulo() const { return mod; }
};
template <class Uint>
class MIntPro_Na {
using DUint = conditional_t<is_same_v<Uint, u32>, u64, u128>;
const Uint mod;
public:
constexpr MIntPro_Na(Uint m) : mod(m) {}
constexpr Uint mul(Uint l, Uint r) const { return DUint(l) * r % mod; }
#define BOP(m, p) return l m## = mod & -((l p## = r) >= mod)
constexpr Uint plus(Uint l, Uint r) const { BOP(-, +); }
constexpr Uint diff(Uint l, Uint r) const { BOP(+, -); }
#undef BOP
constexpr Uint set(Uint n) const { return n % mod; }
constexpr Uint get(Uint n) const { return n; }
constexpr Uint norm(Uint n) const { return n; }
constexpr Uint modulo() const { return mod; }
};
template <class Uint, class mod_pro_t>
constexpr Uint pow(Uint x, u64 k, const mod_pro_t &md) {
for (Uint ret = md.set(1);; x = md.mul(x, x))
if (k & 1 ? ret = md.mul(ret, x) : 0; !(k >>= 1)) return ret;
}
} // namespace math_internal
namespace math_internal {
template <class Uint, class mod_pro_t, u64... args>
constexpr bool miller_rabin(Uint n) {
const mod_pro_t md(n);
const Uint s = __builtin_ctzll(n - 1), d = n >> s, one = md.set(1),
n1 = md.norm(md.set(n - 1));
for (auto a : {args...}) {
Uint b = a % n, p = pow(md.set(b), d, md), i = s;
while (p = md.norm(p), (p != one && p != n1 && b && i--)) p = md.mul(p, p);
if (md.norm(p) != n1 && i != s) return false;
}
return true;
}
constexpr bool is_prime(u64 n) {
if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
if (n < UINT_MAX) return miller_rabin<u32, MIntPro_Na<u32>, 2, 7, 61>(n);
if (n < LLONG_MAX)
return miller_rabin<u64, MIntPro_Montg, 2, 325, 9375, 28178, 450775,
9780504, 1795265022>(n);
return miller_rabin<u64, MIntPro_Na<u64>, 2, 325, 9375, 28178, 450775,
9780504, 1795265022>(n);
}
} // namespace math_internal
using math_internal::is_prime;
namespace math_internal {
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, size_t _Nm>
struct ConstexprArray {
constexpr 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] = {};
size_t sz = 0;
};
class Factors : public ConstexprArray<pair<u64, uint16_t>, 16> {
template <class Uint, class mod_pro_t>
static constexpr Uint rho(Uint n, Uint c) {
const mod_pro_t md(n);
auto f = [&md, n, c](Uint x) { return md.plus(md.mul(x, x), c); };
const Uint m = 1LL << (__lg(n) / 5);
Uint x = 1, y = md.set(2), z = 1, q = md.set(1), g = 1;
for (Uint r = 1, i = 0; g == 1; r <<= 1) {
for (x = y, i = r; i--;) y = f(y);
for (Uint k = 0; k < r && g == 1; g = gcd(md.get(q), n), k += m)
for (z = y, i = min(m, r - k); i--;)
y = f(y), q = md.mul(q, md.diff(y, x));
}
if (g == n) do {
z = f(z), g = gcd(md.get(md.diff(z, x)), n);
} while (g == 1);
return g;
}
static constexpr u64 find_prime_factor(u64 n) {
if (is_prime(n)) return n;
for (u64 i = 100; i--;)
if (n = n < UINT_MAX ? rho<u32, MIntPro_Na<u32>>(n, i + 1)
: n < LLONG_MAX ? rho<u64, MIntPro_Montg>(n, i + 1)
: rho<u64, MIntPro_Na<u64>>(n, i + 1);
is_prime(n))
return n;
return 0;
}
constexpr void init(u64 n) {
for (u64 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 (u64 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(u64 n) { init(n), bubble_sort(dat, dat + sz); }
};
template <class Uint, class mod_pro_t>
constexpr Uint inner_primitive_root(Uint p) {
const mod_pro_t md(p);
const auto f = Factors(p - 1);
for (Uint ret = 2, one = md.set(1), pw = 0, x = 0, k = 0, ng = 0;; ret++) {
for (auto [q, e] : f)
if (ng = (md.norm(pow(md.set(ret), (p - 1) / q, md)) == one)) break;
if (!ng) return ret;
}
}
constexpr u64 primitive_root(u64 p) {
if (assert(is_prime(p)); p == 2) return 1;
if (p < UINT_MAX) return inner_primitive_root<u32, MIntPro_Na<u32>>(p);
if (p < LLONG_MAX) return inner_primitive_root<u64, MIntPro_Montg>(p);
return inner_primitive_root<u64, MIntPro_Na<u64>>(p);
}
} // namespace math_internal
using math_internal::Factors, math_internal::primitive_root;
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)); }
template <class Int>
constexpr inline Int mod_inv(Int a, Int mod) {
static_assert(std::is_signed_v<Int>);
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;
}
namespace math_internal {
template <class Int, class mod_pro_t>
Int peth_root(Int c, Int pi, int ei, const mod_pro_t &md) {
const Int p = md.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 = mod_inv(pe - s % pe, pe), ONE = md.set(1),
z = pow(c, (s * u + 1) / pe, md), zpe = md.norm(pow(c, s * u, md));
if (zpe == ONE) return z;
Int ptm1 = 1, vs, base;
for (int i = t; --i;) ptm1 *= pi;
for (Int v = md.set(2);; v = md.plus(v, ONE))
if (vs = pow(v, s, md), base = md.norm(pow(vs, ptm1, md)); base != ONE)
break;
int size = 1 << std::__lg(int(std::sqrt(pi)) + 1), mask = size - 1,
os[size + 1] = {};
std::pair<Int, int> vec[size];
Int x = ONE, vspe = pow(vs, pe, md);
for (int i = 0; i < size; i++, x = md.mul(x, base)) os[md.norm(x) & mask]++;
for (int i = 1; i < size; i++) os[i] += os[i - 1];
x = ONE, os[size] = size;
for (int i = 0; i < size; i++, x = md.norm(md.mul(x, base)))
vec[--os[x & mask]] = {x, i};
for (int vs_e = ei, td; zpe != ONE;) {
Int tmp = zpe;
for (td = 0; tmp != ONE; td++) tmp = md.norm(pow(tmp, pi, md));
for (int e = t - td; vs_e != e; vs_e++)
vs = pow(vs, pi, md), vspe = pow(vspe, pi, md);
base = md.set(mod_inv<Int>(md.get(zpe), p));
for (int i = 1; i < td; i++) base = pow(base, pi, md);
base = md.norm(base);
for (int tt = 0, upd = 1, n; upd;
tt += size, base = md.norm(md.mul(base, x)))
for (int m = (base & mask), i = os[m]; i < os[m + 1]; i++)
if (base == vec[i].first) {
if (n = vec[i].second - tt; n < 0) n += pi;
z = md.mul(z, pow(vs, n, md)),
zpe = md.norm(md.mul(zpe, pow(vspe, n, md))), upd = false;
break;
}
}
return z;
}
template <class Int, class mod_pro_t>
Int inner_kth_root(Int a, u64 k, Int p) {
if (k == 0) return a == 1 ? a : -1;
if (a <= 1 || k <= 1) return a;
const mod_pro_t md(p);
Int g = std::gcd(k, p - 1), ma = md.set(a);
Int pp = (p - 1) / g, kk = (k / g) % pp;
if (md.norm(pow(ma, pp, md)) != md.set(1)) return -1;
ma = pow(ma, mod_inv(kk, pp), md);
for (auto [pi, ei] : Factors(g)) ma = peth_root<Int>(ma, pi, ei, md);
return md.get(ma);
}
std::int64_t mod_kth_root(std::int64_t a, u64 k, std::int64_t p) {
if (a %= p; p < INT_MAX) return inner_kth_root<int, MIntPro_Na<u32>>(a, k, p);
return inner_kth_root<std::int64_t, MIntPro_Montg>(a, k, p);
}
} // namespace math_internal
using math_internal::mod_kth_root;
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 << mod_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 << mod_kth_root(a, k, p) << '\n';
}
return 0;
}
} // namespace yukicoder981
signed main() {
// yosupo_kth_root::main();
yukicoder981::main();
return 0;
}