本文转载（或修改）自 OI-Wiki
描述
给定多项式 \(G\left(x, y\right)\)，已知多项式 \(f\left(x\right)\) 满足：
\[
G\left(x, f\left(x\right)\right)\equiv 0\pmod{x^{n}}
\]
且存在数值 \(f_1\) 使 \(G\left(x, y\right)\) 满足以下条件：
- \(G(0, f_1) = 0\)；
- \(\frac{\partial G}{\partial y}(0, f_1) \neq 0\)。
求出模 \(x^{n}\) 意义下的 \(f\left(x\right)\)。
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\left(x\right) = f_n\left(x\right)\)。
将 \(G\left(x, f(x)\right)\) 对 \(f(x)\) 在 \(f(x)=f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\) 处进行 Taylor 展开，有：
\[
\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}}
\]
则：
\[
\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}}
\]
或者
\[
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}}
\]
例题
多项式求逆
设给定函数为 \(h\left(x\right)\)，有：
\[
G\left(x, y\right)=\frac{1}{y}-h\left(x\right)
\]
应用 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}
\]
时间复杂度
\[
T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right)
\]
多项式开方
设给定函数为 \(h\left(x\right)\)，有：
\[
G\left(x, y\right)=y^{2}-h\left(x\right)\equiv 0
\]
应用 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}
\]
时间复杂度
\[
T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right)
\]
多项式指数函数
设给定函数为 \(h\left(x\right)\)，有：
\[
G\left(x, y\right)=\ln{y}-h\left(x\right)
\]
应用 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}
\]
时间复杂度
\[
T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right)
\]