多项式除法及求模

问题是这样的:给定一个 n 次多项式 A(x) 和一个 m(m \leq n) 次多项式 B(x),要求求出两个多项式 D(x), R(x),满足

 \begin{equation} \label{div0} A(x) = D(x)B(x) + R(x) \end{equation}

并且 deg D \leq degA - degB = n - mdegR < m

在解决这个问题之前你需要掌握多项式求逆,利用快速傅里叶变换可以在 \mathcal O(n\log n) 的复杂度内求出这个问题的解

多项式除法在很多问题中都有应用,例如多项式的扩展欧几里得算法、线性递推的优化等等

(more…)

Read More