泰勒展开 & 倍增
对于给定 \(G(x)\) 求满足 \(G(F(x))\equiv 0\pmod{x^n}\) 的 \(F(x)\).
假设当前已知 \(G(F_0(x))\equiv 0\pmod{x^{\lceil\frac{n}{2}\rceil}}\), 将 \(G(F(x))\) 在 \(F_0(x)\) 处泰勒展开, 则
\[ \begin{aligned} G(F(x))&=\sum_{i=0}^{+\infty}\frac{G^{(i)}(F_0(x))}{i!}(F(x)-F_0(x))^i\&\equiv G(F_0(x))+G'(F_0(x))(F(x)-F_0(x))\equiv 0&\pmod{&x^n} \F(x)&\equiv F_0(x)-\frac{G(F_0(x))}{G'(F_0(x))}&\pmod{&x^n} \end{aligned} \]
来源: http://www.bubuko.com/infodetail-3375421.html