多项式除法（代数） 学习笔记
注意，本文与「快速数论变换 NTT」无关，是一种代数计算技巧
多项式除法是代数中的一种算法，可以快速手算出一个同次或低次的多项式去除另一个多项式的结果。
事实上，小学学的竖式除法就是该算法在 \(x = 10\) 时的特殊求解方法。
例：考虑计算 \[ \dfrac{x^3-12 x^2-42}{x-3} \] 解：
首先把分子和分母均以降幂排列，缺项补零 \[ \frac{x^3-12 x^2+0 x-42}{x-3} \]
将分子的第一项除以分母的最高次项（即 \(x^3 \div x = x^2\)）
将分母乘以首商，乘积写在分子前两项（同类项对齐）（\(x^2 \cdot(x-3)=x^3-3 x^2\)）
从分子相应项中减去刚刚得到的乘积，得到第一余式 \(-9x^2\) 并写在下方，然后将分子的下一次项拿出来
接下来就把 \(-9x^2 + 0x\) 当作新的被除式，重复前三步
最后得到下式，余式小于除式次数，运算结束
横线之上的多项式即为商，而剩下的 \(-123\) 就是余数，则 \[ \frac{x^3-12 x^2-42}{x-3}=\underbrace{x^2-9 x-27}_{q(x)} \underbrace{-\frac{123}{x-3}}_{r(x) / g(x)} \]
参考文献：
