多项式除法

多项式除法

科技前沿 • 2025-03-19 09:13 • 阅读 54

大家好，我是讯享网，很高兴认识大家。

定义：

对于一个给定的多项式：

其中：

A(X):被除数多项式，次数界为n

B(X):除数多项式，次数界为m(m<n)

D(X):商多项式，次数界为n-m+1

R(X):余数多项式，次数界小于m(余数要小于除数，对于多项式来说就是余数的次数界要小于除数的次数界)

$A(X)A^{-1}(X)=1 (mod \, \, \, \, x^{n})$

A(X)与 $A^{-1}(X)$ 互为逆元

mod $x^{n}$ :模 $x^{n}$ 就是去除掉多项式里 $\geqslant$ n次的项

了解了上述的知识后，我们就可以开始对多项是取模了

$A(X)=R(X)\: \, (mod\, \, \, \, B(X))$

我们要求的有两个：商多项式(D(X)),余数多项式(R(X))

我们先考虑求商，因为求出商之后，余数自然而然的就可以得到了

先用1/x代x $A(\frac{1}{X})=B(\frac{1}{X})D(\frac{1}{X})+R(\frac{1}{X})$

两边在同时乘上 $x^{n}$ $x^{n}A(\frac{1}{x})=x^{m}B(\frac{1}{x})x^{n-m}D(\frac{1}{x})+x^{n-m+1}x^{m-1}R(\frac{1}{x})$

这里我们引入多项式系数的反转：

$Pr(x)=x^{n}P(\frac{1}{x})=\sum_{i=0}^{n}a\textup{n-i}*x^{i}$

所以我们得到： $Ar(x)=Br(x)Dr(x)+x^{n-m+1}Rr(x)$

$Ar(x)=Br(x)Dr(x)(mod \, \, \, \, x^{n-m+1})$

下面求Br(x)的逆元在乘上Ar(x)就得到了Dr(x),在求一次系数反转就得到了D(x)

之后就可以很容易得出Rx()

我们也可以模拟长除法，当余式为0，或者余式次数低于除式时为止，这是商就是D(x),余式就是R(X)