sqrt

関数 · 形式的冪級数 (FPS)

// (1)
template <internal::static_modint_c mint>
std::vector<mint> sqrt(const std::vector<mint> &h, int deg);

// (2)
template <internal::static_modint_c mint>
std::vector<mint> sqrt(const std::vector<mint> &h);

概要

(1) 平方根 $\sqrt h \pmod{x^{deg}}$

$g^2 \equiv h \pmod{x^{deg}}$ を満たす $g$ を求める。最低次の項 $c x^k$ を括り出し、 $k$ が偶数かつ $c$ が平方剰余のとき $g = x^{k/2} \sqrt{h / x^k}$ をニュートン法で求める。 ニュートン法は $g = \sqrt{\cdot}$ と $g^{-1}$ を併走させ各段で DFT を使い回す （full inverse の再計算を避ける）。条件を満たせば Montgomery + AVX2 NTT 実装へ振り分ける。 $k$ が奇数、または $c$ が平方非剰余で解が存在しない場合は空列を返す。

• テンプレートパラメータ mint: static modint
• パラメータ h: 係数列
• パラメータ deg: 求める項数
• 戻り値: std::vector<mint> $g^2 \equiv h$ を満たす $g$（長さ deg）。解なしのときは空列
• 計算量: deg を $d$ として $O(d \log d)$

(2) 平方根 $\sqrt h$（deg は h.size()）

• テンプレートパラメータ mint: static modint
• パラメータ h: 係数列
• 戻り値: std::vector<mint> 長さ h.size() の $\sqrt h$。解なしのときは空列
• 計算量: $n = |h|$ として $O(n \log n)$

関連項目

• plus — 形式的冪級数の加算
• inv — 逆元 $1 / h \pmod{x^{deg}}$
• log — 対数 $\log h \pmod{x^{deg}}$
• exp — 指数 $\exp h \pmod{x^{deg}}$
• pow — 冪乗 $h^m \pmod{x^{deg}}$
• composition — 合成 (composition) $f(g(x)) \pmod{x^{deg}}$
• compositional_inverse — 合成逆 (compositional inverse) $g \pmod{x^{deg}}$
• div_mod — 多項式の除算 (商と剰余)
• div — 多項式の商 f / g
• mod — 多項式の剰余 f mod g
• multipoint_evaluation — 多点評価
• polynomial_interpolation — 多項式補間 (ラグランジュ補間)
• taylor_shift — Taylor shift (係数の平行移動)
• shift_of_sampling_points — 標本点のシフト (shift of sampling points)
• inv_of_polynomials — 多項式の逆元 (modular inverse of polynomials)