多项式计算台 · 04 A

每次只消掉一个最高项

除法的关键是找到一个倍数，让最高项相减后归零。系数到了有限域里，“除以 b”要换成乘以 b 的模逆元。

从常数项到最高次项，用逗号分隔整数。例如 1,2,0,1 表示 1 + 2x + x³。输入系数按模 p 归一化，除式不能为零。

最高项消去记录

相减前的多项式
本步减去的倍式
相减后 / 当前余下

实线框 标出本步要消的最高项；虚线框标出用来相减的同次项。每一列都在模 p 下相减。

换个例子，检查条件

试着把除式改成常数 2，再分别选 F₂ 和 F₃。在 F₂ 中它就是零，不能拿来做除式；在 F₃ 中，2 有逆元 2，除法可以继续。

这里比较的是形式多项式的系数。即使两个多项式在有限域里处处取相同值，它们也未必是同一个多项式。