多项式全家桶

标签：AB log pmod 多项式 全家 2n equiv

多项式求逆

考虑倍增。

若已经求出 \(A \times B' \equiv 1 \pmod {x^n}\)，我们希望求出 \(B\) 使得 \(A \times B \equiv 1 \pmod {x^{2n}}\)。

有：

\[B - B' \equiv 0 \pmod {x^n} \]

\[(B - B')^2 \equiv 0 \pmod {x^{2n}} \]

\[B^2 - 2 B B' + B'^2 \equiv 0 \pmod {x^{2n}} \]

两边同乘 \(A\)，有：

\[B - 2B' + AB'^2 \equiv 0 \pmod {x^{2n}} \]

所以：

\[B \equiv 2B' - AB'^2 \pmod {x^{2n}} \]

注意应该倍增到最小的 \(2^t\) 使得 \(2^t \ge n\)。

时间复杂度 \(O((n + \frac{n}{2} + \frac{n}{4} + \cdots) \log n) = O(n \log n)\)。

标签：AB,log,pmod,多项式,全家,2n,equiv
From： https://www.cnblogs.com/zltzlt-blog/p/18146944