kth_root_mod

関数 · 素数法上で x の平方根を 1 つ返す

template <internal::modint mint>
std::optional<mint> kth_root_mod(mint a, std::int64_t k);

概要

$K$ 乗根 $\bmod P$（$P$ は素数）を 1 つ求める

$x^K \equiv a \pmod P$ なる $x$ を Adleman-Manders-Miller アルゴリズムで求める。 $0^0 \equiv 1$ の規約に従う。$\gcd(K, P - 1)$ の素因数ごとに internal::peth_root を適用して合成する。

テンプレートパラメータ

パラメータ

戻り値

条件を満たす $x$ の 1 つ。解が存在しないときは std::nullopt

計算量

• 法を $P$ として $O(\sqrt P\log^2 P)$

関連項目

• sqrt_mod — 素数法上で x の平方根を 1 つ返す