多项式除法|取模

描述

给定多项式 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)


评论