「Learning Notes」多项式除法&取模

Description

给定多项式 f(x), g(x) ,求 g(x) f(x) 的商 Q(x) 和余数 R(x)

Method

发现若能消除 R(x) 的影响则可直接多项式求逆解决.
考虑构造变换

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

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

n = \operatorname{deg}{f}, m = \operatorname{deg}{g}
f(x) = Q(x) g(x) + R(x) 中的 x 替换成 \frac{1}{x} 并将其两边都乘上 x^{n} ,得到:

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

注意到上式中 R^{R}(x) 的系数为 x^{n - m + 1} ,则将其放到模 x^{n - m + 1} 意义下即可消除 R^{R}(x) 带来的影响。
又因 Q^{R}(x) 的次数为 \left(n - m\right)<\left(n - m + 1\right) ,故 Q^{R}(x) 不会受到影响。
则:

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

使用多项式求逆即可求出 Q(x) ,将其反代即可得到 R(x)

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

Examples