多项式牛顿迭代

· · 个人记录

描述

给定多项式 G(x,y)，求出 f(x) 满足：

G(x,f(x))\equiv 0 \mod x^n

不是很好理解，可以把 G(x,y) 看成一个复合函数，带入 f(x) 即为 G(f(x))。

方法

考虑倍增。

当前算出了

G(f_m(x))\equiv 0 \mod x^m

需要求出

G(f_{2m}(x))\equiv 0 \mod x^{2m}

而公式即为：

f_{2m}(x)\equiv f_m(x)-\frac{G(f_m(x))}{G'(f_m(x))}\mod x^{2m}

证明以及使用的条件参考oi-wiki。反正我只要会牛顿迭代 exp 就行了。