多项式除法|取模

描述

给定多项式 $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)$ 中的替换成 $\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)$ 。

本页面最近更新：2021/2/8 18:02:48，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：97littleleaf11, Enter-tainer, H-J-Granger, Ir1d, SamZhangQingChuan, sshwy, TrisolarisHD
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用