「Learning Notes」多项式开方

本文会随着笔者的水平提升持续更新.
若发现文中有叙述不严谨之处,欢迎指出。

Description

给定多项式 g(x) ,求 f(x) ,满足:

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

Methods

倍增法

假设现在已经求出了 g(x) 在模 x^{\left\lceil\frac{n}{2}\right\rceil} 意义下的平方根 f_{0}(x) ,则有:

\begin{aligned} f_{0}^{2}(x) & \equiv g(x) & \pmod{x^{\left\lceil\frac{n}{2}\right\rceil}}\\ f_{0}^{2}(x) - g(x) & \equiv 0 & \pmod{x^{\left\lceil\frac{n}{2}\right\rceil}}\\ \left(f_{0}^{2}(x) - g(x)\right)^{2} & \equiv 0 & \pmod{x^{n}}\\ \left(f_{0}^{2}(x) + g(x)\right)^{2} & \equiv 4 f_{0}^{2}(x) g(x) & \pmod{x^{n}}\\ \left(\frac{f_{0}^{2}(x) + g(x)}{2 f_{0}(x)}\right)^{2} & \equiv g(x) & \pmod{x^{n}}\\ \frac{f_{0}^{2}(x) + g(x)}{2 f_{0}(x)} & \equiv f(x) & \pmod{x^{n}}\\ 2^{-1} f_{0}(x) + 2^{-1} f_{0}^{-1}(x) g(x) & \equiv f(x) & \pmod{x^{n}} \end{aligned}

倍增计算即可。

时间复杂度

T(n) = T\left(\frac{n}{2}\right) + O(n \log{n}) = O(n \log{n})

还有一种常数较小的写法就是在倍增维护 f(x) 的时候同时维护 f^{-1}(x) 而不是每次都求逆。

\left[x^{0}\right] g(x) \ne 1 时,可能需要使用二次剩余来计算 \left[x^{0}\right] f(x)

Newton's Method

参见 Newton's Method.

Examples

  1. 「Codeforces Round #250」E. The Child and Binary Tree