本文是基于 oi-wiki 整理的，大部分是照抄，修改了少量错误；和本博客、oi-wiki 原文一样遵循 CC BY-SA 4.0 协议。

适用问题

给定多项式 $g(x)$，已知有 $f(x)$ 满足

$$g(f(x)) \equiv 0 \pmod{x^n}$$

求模 $x^n$ 意义下的 $f(x)$。

内容

推导过程要用泰勒展开，不会（

考虑倍增。当 $n = 1$ 时，$[x^0] g(f(x)) = 0$ 的解需要单独求出，否则

$$f(x) \equiv f_0(x) - \frac{g(f_0(x))}{g'(f_0(x))} \pmod {x^n}$$

使用例

多项式求逆

设给定函数为 $h(x)$，有

$$g(f(x)) = \frac 1{f(x)} - h(x) \equiv 0 \pmod{x^n} \\ \begin{align} f(x) & \equiv f_0(x) - \frac{ \frac 1{f_0(x)} - h(x)}{- \frac 1{f_0^2}(x)} & \pmod{x^n} \\ & \equiv 2 f_0(x) - f_0^2(x) h(x) &\pmod{x^n} \end{align}$$

这个式子和前面直接推的是一样的。

多项式开方

设给定函数为 $h(x)$，有

$$g(f(x)) = f^2(x) - h(x) \equiv 0 \pmod{x^n} \\ \begin{align} f(x) & \equiv f_0(x) - \frac{f_0^2(x) - h(x)}{2 f_0(x)} & \pmod{x^n} \\ & \equiv \frac{f_0(x) + f_0^{-1}(x) h(x)}2 & \pmod{x^n} \end{align}$$

这个式子和前面直接推的是一样的。

多项式 exp

设给定函数为 $h(x)$，有

$$g(f(x)) = \ln f(x) - h(x) \pmod{x^n} \\ \begin{align} f(x) & \equiv f_0(x) - \frac{\ln f_0(x) - h(x)}{\frac 1{f_0(x)}} & \pmod{x^n} \\ & \equiv f_0(x)(1 - \ln f_0(x) + h(x)) & \pmod{x^n} \end{align}$$

这个的复杂度是 $O(n \log n)$。