企业官网建设流程全解析

OI-wiki 多项式牛顿迭代法（Newton's Method）详解：从泰勒展开推导到代数完备性证明

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

导读

本文以 OI-wiki 多项式章节中的 newton.md 为主体，系统讲解求解形如 $G(x, f(x))\equiv 0 \pmod{x^{n}}$ 隐式多项式方程的统一算法——多项式牛顿迭代法（Newton's Method）。作为 多项式初等函数 家族（求逆、开方、指数、对数、三角函数等）的底层引擎，掌握它即可一通百通：读完本文你将理解其倍增递推式的来源、迭代格式 $f_{2n}=f_n-G(f_n)/G'(f_n)$ 的导出过程、三大经典应用（多项式求逆、多项式开方、多项式指数函数）如何统一在一个框架下，并能结合手算演示与抽象代数证明理解算法的可解性条件与解的唯一性。

问题描述：在形式幂级数环上解方程

给定二元多项式 $G(x, y)$，已知多项式 $f(x)$ 满足：

$$ G\left(x, f\left(x\right)\right)\equiv 0\pmod{x^{n}} $$

且存在数值 $f_1$ 使 $G(x, y)$ 满足以下条件：

• $G(0, f_1) = 0$；
• $\dfrac{\partial G}{\partial y}(0, f_1) \neq 0$．

目标是求出模 $x^{n}$ 意义下的 $f(x)$。

这里的数学背景是 形式幂级数环 $R[[x]]$：如 intro.md 所述，模 $x^n$ 的操作等价于"截断"——将无穷项的幂级数截断到前 $n$ 项。因此"模 $x^n$ 意义下求解"实质上是逐级逼近真实幂级数的过程，这为倍增思想提供了天然舞台。初始条件中的 $f_1$ 相当于方程的"根"，而偏导数条件 $\frac{\partial G}{\partial y}(0, f_1) \neq 0$ 保证根是"单根"（简单根），这是后续每一步迭代中求逆可进行的必要条件。

Newton's Method：核心推导

考虑倍增策略。

初始步：当 $n=1$ 时，$\left[x^{0}\right]G\left(x, f\left(x\right)\right)=0$ 的解需要单独求出，问题假设中的 $f_1$ 即为一个解。

归纳步：假设已经得到模 $x^{\left\lceil\frac{n}{2}\right\rceil}$ 意义下的解 $f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)$，要求模 $x^{n}$ 意义下的解 $f_n\left(x\right)$。

将 $G(x, f(x))$ 对 $f(x)$ 在 $f(x)=f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)$ 处进行泰勒展开：

$$ \sum_{i=0}^{+\infty}\frac{\frac{\partial^i G}{\partial y^i}\left(x, f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)}{i!}\left(f\left(x\right)-f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)^{i}\equiv 0\pmod{x^{n}} $$

关键的截断观察在于：因为 $f\left(x\right)-f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)$ 的最低非零项次数最低为 $\left\lceil\frac{n}{2}\right\rceil$，故有：

$$ \forall 2\leqslant i:\left(f\left(x\right)-f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)^{i}\equiv 0\pmod{x^{n}} $$

也就是说，差值的高次幂在模 $x^n$ 意义下全部消失，泰勒展开只需保留到一阶项：

$$ \begin{aligned} \sum_{i=0}^{+\infty}\frac{\frac{\partial^i G}{\partial y^i}\left(x, f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)}{i!}\left(f\left(x\right)-f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)^{i}&\equiv G\left(x, f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)+\frac{\partial G}{\partial y}\left(x, f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)\left[f\left(x\right)-f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right]\ &\equiv 0\pmod{x^{n}} \end{aligned} $$

移项整理即得倍增迭代格式：

$$ f_n\left(x\right)\equiv f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)-\frac{G\left(x, f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)}{\frac{\partial G}{\partial y}\left(x, f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)}\pmod{x^{n}} $$

或者写成更便于实现的精度翻倍形式（从 $n$ 位翻倍到 $2n$ 位）：

$$ f_{2n}\left(x\right)\equiv f_n\left(x\right)-\frac{G\left(x, f_n\left(x\right)\right)}{\frac{\partial G}{\partial y}\left(x, f_n\left(x\right)\right)}\pmod{x^{2n}} $$

这与实数的 牛顿迭代法 $x_{i+1}=x_i-\frac{f(x_i)}{f'(x_i)}$ 在形式上完全同构：在实数域上迭代收敛位数翻倍（平方收敛），在形式幂级数环上则表现为"精度位数翻倍"——每次迭代把已知解从模 $x^n$ 提升到模 $x^{2n}$，因而总复杂度满足 $T(n)=T(n/2)+O(n\log n)$。

例题：三大初等函数如何统一进牛顿框架

多项式求逆

参见 elementary-func.md#多项式求逆。设给定函数为 $h(x)$，构造：

$$ G\left(x, y\right)=\frac{1}{y}-h\left(x\right) $$

此时 $\frac{\partial G}{\partial y}=-\frac{1}{y^2}$。应用 Newton's Method：

$$ \begin{aligned} f_{2n}\left(x\right)&\equiv f_{n}\left(x\right)-\frac{1/f_{n}\left(x\right)-h\left(x\right)}{-1/f_{n}^{2}\left(x\right)}&\pmod{x^{2n}}\ &\equiv 2f_{n}\left(x\right)-f_{n}^{2}\left(x\right)h\left(x\right)&\pmod{x^{2n}} \end{aligned} $$

这就是广为人知的求逆倍增公式 $f_{2n}=f_n(2-f_nh)$。仓库中 elementary-func.md 给出的polyinv实现正是这一格式的直接编码：

void polyinv(const poly &h, const int n, poly &f) { /* f = 1 / h = f_0 (2 - f_0 h) */ static poly_t inv_t; std::fill(f, f + n + n, 0); f[0] = fpow(h[0], mod - 2); for (int t = 2; t <= n; t <<= 1) { const int t2 = t << 1; std::copy(h, h + t, inv_t); std::fill(inv_t + t, inv_t + t2, 0); DFT(f, t2); DFT(inv_t, t2); for (int i = 0; i != t2; ++i) f[i] = (i64)f[i] * sub(2, (i64)f[i] * inv_t[i] % mod) % mod; IDFT(f, t2); std::fill(f + t, f + t2, 0); } }

注意初始化f[0] = fpow(h[0], mod - 2)正是牛顿法"单独解出 $n=1$ 时的初始解"这一步——求逆的常数项即 $h$ 常数项的乘法逆元，这也印证了 intro.md 中"存在倒数当且仅当常数项不为 $0$"的结论。

时间复杂度：

$$ T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right) $$

多项式开方

参见 elementary-func.md#多项式开方。设给定函数为 $h(x)$，构造：

$$ G\left(x, y\right)=y^{2}-h\left(x\right)\equiv 0 $$

此时 $\frac{\partial G}{\partial y}=2y$。应用 Newton's Method：

$$ \begin{aligned} f_{2n}\left(x\right)&\equiv f_{n}\left(x\right)-\frac{f_{n}^{2}\left(x\right)-h\left(x\right)}{2f_{n}\left(x\right)}&\pmod{x^{2n}}\ &\equiv\frac{f_{n}^{2}\left(x\right)+h\left(x\right)}{2f_{n}\left(x\right)}&\pmod{x^{2n}} \end{aligned} $$

仓库中多项式开方的完整可运行参考代码位于 docs/math/code/poly/sqrt/sqrt_1.cpp（洛谷 P5205 模板题），其核心倍增部分与上面的公式一一对应：

void sqrt(int deg, int *f, int *h) { if (deg == 1) { h[0] = 1; return; } sqrt((deg + 1) >> 1, f, h); int len = 1; while (len < deg * 2) { // 倍增 len *= 2; } fill(g, g + len, 0); inv(deg, h, g); // 先求 h 的逆 copy(f, f + deg, t); fill(t + deg, t + len, 0); NTT(t, len, 1); NTT(g, len, 1); NTT(h, len, 1); for (int i = 0; i < len; i++) { h[i] = (long long)1 * inv2 * ((long long)1 * h[i] % mod + (long long)1 * g[i] * t[i] % mod) % mod; } NTT(h, len, -1); fill(h + deg, h + len, 0); }

这段代码展示了牛顿迭代的完整工程细节：递归求解模 $x^{\lceil \deg/2\rceil}$ 的解作为本轮输入（对应 $f_n$）；通过inv求 $f_n$ 的逆元（对应 $1/(2f_n)$ 中的 $1/f_n$）；再用 NTT 点值相乘实现 $f_n^2(x)+h(x)$ 与 $f_n^{-1}(x)$ 的卷积（对应 $\frac{f_n^2+h}{2f_n}$），最后乘上 $2^{-1}=\mathrm{inv2}$。整体乘法均基于模 $998244353$ 的 NTT 完成，ntt_1.cpp 提供了该 NTT 的完整实现。

关于开方的可解性，elementary-func.md#多项式开方 还补充了细节：常数项 $\left[x^0\right]f(x)=\sqrt{\left[x^0\right]g(x)}$ 必须存在平方根（可能需要二次剩余），且上述方法需要 $f_0(x)$ 可逆故常数项不能为 $0$；若 $\left[x^0\right]g(x)=0$，则需分解 $g(x)=x^{k}h(x)$，$k$ 为奇数时无平方根，$k$ 为偶数时开 $h(x)$ 再整体乘 $x^{k/2}$。

时间复杂度：

$$ T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right) $$

多项式指数函数

参见 elementary-func.md#多项式对数函数--指数函数。设给定函数为 $h(x)$，构造：

$$ G\left(x, y\right)=\ln{y}-h\left(x\right) $$

此时 $\frac{\partial G}{\partial y}=\frac{1}{y}$。应用 Newton's Method：

$$ \begin{aligned} f_{2n}\left(x\right)&\equiv f_{n}\left(x\right)-\frac{\ln{f_{n}\left(x\right)}-h\left(x\right)}{1/f_{n}\left(x\right)}&\pmod{x^{2n}}\ &\equiv f_{n}\left(x\right)\left(1-\ln{f_{n}\left(x\right)}+h\left(x\right)\right)&\pmod{x^{2n}} \end{aligned} $$

注意这里要求 $[x^0]h(x)=0$（否则 $\exp$ 的常数项不收敛），而 $[x^0]f_n(x)=1$，这样 $f_n$ 可逆且 $\ln f_n$ 有意义。仓库中 elementary-func.md 的polyexp实现正是此公式的编码，其中每轮迭代内部都要调用一次polyln（它又依赖polyinv）——这体现了牛顿迭代框架的分层嵌套特征：指数函数依赖对数函数与求逆，求逆又依赖 NTT，构成了完整的多项式算法栈。

时间复杂度：

$$ T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right) $$

注：三个例题的时间复杂度形式完全相同，均为 $O(n\log n)$。这与"每次迭代精度翻倍、单次迭代代价为 $O(n\log n)$ 的卷积"这一结构完全匹配。作为对比，elementary-func.md 中提到若不使用牛顿法而用分治 FFT 直接解 $\exp$ 的系数递推，复杂度为 $O(n\log^2 n)$，可见牛顿法的效率优势。

手算演示：把算法跑在纸面上

为了直观理解倍增流程，下面用两组例子逐步演示。

复数多项式模多项式的平方根

假设 $h$ 是一个不被 $x$ 整除（有常数项）的复数多项式，求它对模 $x^n$ 的平方根。方程：

$$ G\left(f(x)\right) = f^2(x)-h(x) \equiv 0\pmod{x^{n}} $$

对 $G$ 作泰勒展开（注意：这里是对 $f$ 展开，导数都是对 $f$ 的偏导数，$x$ 当作常数处理）：

$$ G(f(x)) = \sum_{i=0}^{+\infty}\frac{G^{\left(i\right)}\left(f_{0}(x)\right)}{i!}\left(f(x)-f_{0}(x)\right)^{i} = G(f_0(x)) + 2f_0(x)(f(x)-f_0(x)) + (f(x)-f_0(x))^2 $$

用倍增计算。设倍增中的中间结果是 $f_0(x), f_1(x), \ldots, f_j(x)$，严谨地说 $f_j(x)$ 是满足 $G(f_j(x))\equiv 0\pmod{x^{2^j}}$ 的复数多项式，且为了唯一性同时满足：

• $f_{j}(x)$ 的次数不超过 $2^j-1$（即只保留模 $x^{2^j}$ 内的项）；
• $f_{j+k}(x)-f_j(x)\equiv 0\pmod{x^{2^j}}$，对所有 $k$（后续项在低精度下与当前解一致）。

把 $f_{j+1}(x)$ 和 $f_j(x)$ 代入展开式：

$$ G(f_{j+1}(x)) = G(f_j(x)) + 2f_j(f_{j+1}(x)-f_j(x)) + (f_{j+1}(x)-f_{j}(x))^2 \equiv 0 \pmod{x^{2^{j+1}}} $$

由于 $f_{j+1}(x)-f_j(x)$ 必然是 $x^{2^j}$ 的倍数，其平方被 $x^{2^{j+1}}$ 整除，于是：

$$ f_{j+1}(x) \equiv f_j(x) - \frac{f_j^2(x)-h(x)}{2f_j(x)} \equiv \frac{f_j(x)^2 + h(x)}{2f_j(x)} \pmod{x^{2^{j+1}}} $$

可解性分析：若 $f_j(x)$ 存在，那么 $2f_j(x)$ 不被 $x$ 整除（有常数项），故必然有模 $x^{2^{j+1}}$ 的逆元，下一步迭代总能进行。因此数列 $f_0,f_1,\ldots,f_j$ 存在当且仅当 $f_0$ 存在。而不被 $x$ 整除的复数多项式 $h(x)$ 模 $x$ 的平方根一定存在：$h(x)$ 模掉 $x$ 就是一个普通非零复数，一定有两个平方根。所以对所有有常数项的 $h(x)$ 该算法都适用。

选 $h(x)=x+1$ 实际计算：

• 取 $f_0(x)=1$：$f_1(x)=\dfrac{1^2+x+1}{2\times 1}\mod x^2 = \dfrac{1}{2}x+1$，$f_2(x)=\dfrac{\left(\frac{1}{2}x+1\right)^2+x+1}{2\times \left(\frac{1}{2}x+1\right)}\mod x^4 = \dfrac{1}{16}x^3-\dfrac{1}{8}x^2+\dfrac{1}{2}x+1$，$\ldots$
• 取 $f_0(x)=-1$：$f_1(x)=\dfrac{(-1)^2+x+1}{2\times (-1)}\mod x^2 = -\dfrac{1}{2}x-1$，$\ldots$（结果恰为前一条取负）

可以验证两条都是正确的模平方根多项式列——这正对应平方根的双值性（$\pm$ 两个分支）。

整数模素数幂的平方根

牛顿迭代算法还可迁移到整数模素数幂的情形。假设 $h$ 是一个不被 $3$ 整除的整数，求 $h$ 在模 $3^n$ 意义下的平方根 $f$（"不被 $3$ 整除"保证初始根存在，具体条件后文再言）。方程：

$$ G\left(f\right) = f^2-h \equiv 0\pmod{3^{n}} $$

泰勒展开：

$$ G(f) = \sum_{i=0}^{+\infty}\frac{G^{\left(i\right)}\left(f_{0}\right)}{i!}\left(f-f_{0}\right)^{i} = G(f_0) + 2f_0(f-f_0) + (f-f_0)^2 $$

倍增计算，设中间结果是 $f_0, f_1, \ldots, f_j$，其中 $f_j$ 满足 $G(f_j)\equiv 0\pmod{3^{2^j}}$，且：

• $0 < f_{j} < 3^{2^j}$；
• $f_{j+k}-f_j\equiv 0\pmod{3^{2^j}}$，对所有 $k$。

代入后由于 $f_{j+1}-f_j$ 是 $3^{2^j}$ 的倍数，其平方被 $3^{2^{j+1}}$ 整除：

$$ G(f_{j+1}) = G(f_j) + 2f_j(f_{j+1}-f_j) + (f_{j+1}-f_{j})^2 \equiv 0 \pmod{3^{2^{j+1}}} $$

得：

$$ f_{j+1} \equiv f_j - \frac{f_j^2-h}{2f_j} \equiv \frac{f_j^2 + h}{2f_j} \pmod{3^{2^{j+1}}} $$

可解性分析：若 $f_j$ 存在，则 $2f_j$ 不被 $3$ 整除，故有模 $3^{2^{j+1}}$ 的逆元，迭代总可继续。因此数列存在当且仅当 $f_0$ 存在。而不被 $3$ 整除的整数 $h$ 模 $3$ 的平方根要么不存在，要么有两个。所以$h$ 有模 $3$ 的平方根就是整个算法能跑的唯一条件。

选 $h=46$ 实际计算：

• 取 $f_0=1$：$f_1=\dfrac{1^2+46}{2\times 1}\mod 9 = 1$，$f_2=\dfrac{1^2+46}{2\times 1}\mod 81 = 64$，$f_3=\dfrac{64^2+46}{2\times 64}\mod 6561 = 955$，$\ldots$
• 取 $f_0=2$：$f_1=\dfrac{2^2+46}{2\times 2}\mod 9 = 8$，$f_2=\dfrac{8^2+46}{2\times 8}\mod 81 = 17$，$f_3=\dfrac{17^2+46}{2\times 17}\mod 6561 = 5606$，$\ldots$（等于前一条取负）

可以验证两条都是正确的模平方根数列（模 $3^n$ 意义下 $955 \equiv -5606 \pmod{6561}$ 成立）。

这一节说明牛顿迭代法并非只服务于多项式：在 $\mathbb Z/p^n\mathbb Z$ 这类环上同样成立，其本质是"局部环上的亨泽尔引理（Hensel's lemma）式提升"，这与代数证明部分的抽象化表述是同一思想。

代数证明：为什么一定存在解，以及为什么能得到全部解

前面各节用微积分语言完成了推导与验证，本节用抽象代数的语言把结论一般化并严格化。前提概念（整环、唯一分解整环、形式幂级数环）可参考 抽象代数基本概念。

有解的证明

引理 1（单根提升引理）：设整环 $R$ 有多项式或形式幂级数 $f(X) = \sum_{i\geq 0}a_iX^i$，以及 $r,p\in R$ 使得 $f(r)\in Rp$（即 $r$ 是 $f(X)$ 在模 $p$ 意义下的根）且 $f'(r)\in R$ 在模 $p$ 意义下可逆。这里 $f'(X) := \sum_{i\geq 0}(i+1)a_{i+1}X^i$ 是 $f(X)$ 的形式导数。那么：

$$ f\left(r-\dfrac{f(r)}{f'(r)}\right) \equiv 0\pmod {p^2} $$

证明：对所有 $s\in R$ 展开 $f(r+sp)$：

$$ \begin{aligned} f(r+sp) &= \sum_{i\geq 0}a_i(r+sp)^i \ &= \sum_{i\geq 0}a_ir^i + sp\sum_{i\geq 1}ia_ir^{i-1} + s^2p^2\left(\ldots\right) \ &= f(r) + spf'(r) + s^2p^2\left(\frac{f''(r)}{2!} + \cdots\right), \end{aligned} $$

所以 $f(r+sp) \in Rp^2 \iff f(r)+f'(r)sp \in Rp^2$。因为 $f(r)\in Rp$ 且 $f'(r)$ 可逆，取 $sp = -\dfrac{f(r)}{f'(r)}$ 即可，其中 $\dfrac{1}{f'(r)}$ 是模 $p^2$ 意义下的逆元。$f'(r)$ 在模 $p$ 意义下可逆保证了它在模 $p^2$ 意义下也存在逆元：设有 $a,b,c\in R$ 使 $af'(r) = bp+1$ 和 $f(r)=cp$，那么 $\left(a^2f'(r)-2\right)f'(r) = b^2p^2+1$，故可取 $s=c(2-a^2f'(r))$。∎

对于域 $k$ 上的多项式环 $k[X]$，设 $G(X, Y)\in k[X, Y]$ 和 $f_n\in k[X]$ 使 $G(X, f_n(X))\in k[X]X^n$，应用引理 1（取 $p=X^n$，$r=f_n$）即得：

$$ G\left(X, f_n(X) - \frac{G(X, f_n(X))}{\frac{\partial G}{\partial Y}(X, f_n(X))} \right)\equiv 0 \pmod {X^{2n}} $$

这正是牛顿迭代一步把精度从 $n$ 提到 $2n$ 的代数版本。

归纳启动：倍增的初始条件只需有 $f_1\in k$ 使得 $G(X, f_1)\equiv 0\pmod X$ 且 $\dfrac{\partial G}{\partial Y}(X, f_1)\not\equiv 0\pmod X$。后一个条件保证了 $\dfrac{\partial G}{\partial Y}$ 有非零常数项；又因为 $X$ 整除 $\dfrac{G(X, f_n(X))}{\frac{\partial G}{\partial Y}(X, f_n(X))}$（分子被 $X^n$ 整除、分母常数项非零），故而对所有的 $n$，$\dfrac{\partial G}{\partial Y}(X, f_n)$ 总是模 $X^n$ 意义下可逆的，满足了下一次迭代的条件。于是由归纳法，只要初始单根条件成立，牛顿法对所有 $n$ 都能给出模 $X^n$ 意义下的解。

得到全部解的证明

引理 2（唯一性引理）：若 $R$ 为 唯一分解整环，$f,r,p$ 定义同引理 1，则引理 1 给出的 $r-\dfrac{f(r)}{f'(r)}$ 是模 $p^{2}$ 意义下唯一满足以下两条件的 $x$：

• $f(x)\in Rp^{2}$；
• $x-r\in Rp$。

亦即：

$$ \forall x\in R,\qquad p^2\mid f(x)\wedge p\mid (x-r) \implies x\equiv r-\dfrac{f(r)}{f'(r)} \pmod {p^2} $$

证明：令 $s = -\dfrac{f(r)}{f'(r)p}$，$u = r+sp$。引理 1 保证 $u$ 满足两个条件，且 $f(r) + f'(r)sp \in Rp^{2}$。设 $v$ 是任一满足上述条件的值，则有 $v = r+tp$ 和 $f(r) + f'(r)tp \in Rp^{2}$。两式相减得 $f'(r)(t-s)p\in Rp^{2}$，由于 $f'(r)$ 可逆，故 $v-u\in Rp^{2}$，唯一性得证。∎

完备性论证：牛顿法可以保证得到模 $X^{2^n}$ 的全部解。假设 $G(X, h)\equiv 0\pmod {X^{2^n}}$，令 $h_{2^i} := h\pmod {X^{2^i}}$，取 $f_1 = h_1$ 并用牛顿法，根据引理 2 可得 $f_{2^i} \equiv h_{2^i}\pmod {X^{2^i}}$ 对每个 $i$ 成立，所以一定有 $f_{2^n} = h$。也就是说任意模 $X^{2^n}$ 的解都可以由牛顿法从模 $X$ 的解出发重建出来。

推论：上面的论证还说明，在 $\dfrac{\partial G}{\partial y}(0, y)$ 永远可逆时，$G(X, f)\equiv 0\pmod {X^n}$ 的解的个数等于 $G(0, f)\equiv 0\pmod X$ 的解的个数——即高精度下的解完全由低精度（常数项）下的解决定。这个结论并非平凡，看下面的反例：

牛顿法无效时解的个数随次数变多的例子：模 $X$ 意义下 $X^2$ 的平方根只有 $0$，但是模 $X^4$ 意义下 $X^2$ 的平方根有 $X, -X, X^3+X, \ldots$。此处 $G(X,Y)=Y^2-X^2$ 在 $Y=0$ 处的偏导 $\frac{\partial G}{\partial Y}=2Y$ 恒为零（重根），牛顿法条件 $\frac{\partial G}{\partial y}\neq 0$ 被破坏，于是"每提升一次精度解就分叉"的现象出现，解的个数不再守恒。这个例子从反面凸显了单根条件（偏导数非零）是牛顿法良好行为（存在性 + 完备性）的关键前提。

小结：牛顿法的使用要点

延伸阅读

• 多项式与生成函数：形式幂级数环、乘法逆元、模 $x^n$ 截断等前置概念
• 多项式初等函数：求逆、开方、除法、取模、$\ln$/$\exp$、三角/反三角函数的完整解法与代码
• 快速数论变换 NTT 与 参考实现：牛顿迭代每轮所需的卷积底层
• 多项式开方参考实现：可运行的洛谷 P5205 模板题完整代码
• 抽象代数基本概念：整环、UFD、形式幂级数环的定义与性质
• 数值牛顿迭代法：实数域上的牛顿法及平方根求解，与本文的环上版本互为对照

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki