多项式除法|取模

描述

给定多项式 f\left(x\right),g\left(x\right) ，求 g\left(x\right) 除 f\left(x\right) 的商 Q\left(x\right) 和余数 R\left(x\right) 。

解法

发现若能消除 R\left(x\right) 的影响则可直接 多项式求逆 解决。

考虑构造变换

f^{R}\left(x\right)=x^{\operatorname{deg}{f}}f\left(\frac{1}{x}\right)

观察可知其实质为反转 f\left(x\right) 的系数。

设 n=\operatorname{deg}{f},m=\operatorname{deg}{g} 。

将 f\left(x\right)=Q\left(x\right)g\left(x\right)+R\left(x\right) 中的 x 替换成 \frac{1}{x} 并将其两边都乘上 x^{n} ，得到：

\begin{aligned} x^{n}f\left(\frac{1}{x}\right)&=x^{n-m}Q\left(\frac{1}{x}\right)x^{m}g\left(\frac{1}{x}\right)+x^{n-m+1}x^{m-1}R\left(\frac{1}{x}\right)\\ f^{R}\left(x\right)&=Q^{R}\left(x\right)g^{R}\left(x\right)+x^{n-m+1}R^{R}\left(x\right) \end{aligned}

注意到上式中 R^{R}\left(x\right) 的系数为 x^{n-m+1} ，则将其放到模 x^{n-m+1} 意义下即可消除 R^{R}\left(x\right) 带来的影响。

又因 Q^{R}\left(x\right) 的次数为 \left(n-m\right)<\left(n-m+1\right) ，故 Q^{R}\left(x\right) 不会受到影响。

则：

f^{R}\left(x\right)\equiv Q^{R}\left(x\right)g^{R}\left(x\right)\pmod{x^{n-m+1}}

使用多项式求逆即可求出 Q\left(x\right) ，将其反代即可得到 R\left(x\right) 。

时间复杂度 O\left(n\log{n}\right) 。

buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article OI-wiki
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Comments