欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

多项式除法

程序员文章站 2022-08-12 14:40:11
给定多项式F(x)F(x)F(x)和G(x)G(x)G(x),求F(x)F(x)F(x)除以G(x)G(x)G(x)的商Q(x)Q(x)Q(x)和余数R(x)R(x)R(x)。即F(x)=Q(x)G(x)+R(x)Deg(R)

给定多项式 F ( x ) F(x) F(x) G ( x ) G(x) G(x),求 F ( x ) F(x) F(x)除以 G ( x ) G(x) G(x)的商 Q ( x ) Q(x) Q(x)和余数 R ( x ) R(x) R(x)。即
F ( x ) = Q ( x ) G ( x ) + R ( x ) D e g ( R ) < D e g ( G ) < D e g ( F ) F(x)=Q(x)G(x)+R(x)\quad Deg(R)<Deg(G)<Deg(F) F(x)=Q(x)G(x)+R(x)Deg(R)<Deg(G)<Deg(F)
首先构造
F R ( x ) = x D e g ( F ) F ( 1 x ) F^R(x)=x^{Deg(F)}F(\frac{1}{x}) FR(x)=xDeg(F)F(x1)
这个东西就是将系数反转。比如
F ( x ) = x 4 + 2 x 3 + 3 x 2 + 4 x + 5 F R ( x ) = 5 x 4 + 4 x 3 + 3 x 2 + 2 x 1 \begin{aligned} F(x)&=x^4+2x^3+3x^2+4x+5\\ F^R(x)&=5x^4+4x^3+3x^2+2x1 \end{aligned} F(x)FR(x)=x4+2x3+3x2+4x+5=5x4+4x3+3x2+2x1
n = D e g ( F ) , m = D e g ( G ) n=Deg(F),m=Deg(G) n=Deg(F),m=Deg(G),则 n − m = D e g ( Q ) n-m=Deg(Q) nm=Deg(Q)
那么就有
F ( x ) = Q ( x ) G ( x ) + R ( x ) x n F ( x ) = x n Q ( x ) G ( x ) + x n R ( x ) x n F ( 1 x ) = x n − m Q ( 1 x ) x m G ( 1 x ) + x n − m + 1 x m − 1 R ( 1 x ) F R ( x ) = Q R ( x ) G R ( x ) + x n − m + 1 x m − 1 R ( 1 x ) F R ( x ) ≡ Q R ( x ) G R ( x )    m o d    x n − m + 1 F R ( x ) [ G R ( x ) ] − 1 ≡ Q R ( x )    m o d    x n − m + 1 \begin{aligned} F(x)&=Q(x)G(x)+R(x)\\ x^nF(x)&=x^nQ(x)G(x)+x^nR(x)\\ x^nF(\frac{1}{x})&=x^{n-m}Q(\frac{1}{x})x^mG(\frac{1}{x})+x^{n-m+1}x^{m-1}R(\frac{1}{x})\\ F^R(x)&=Q^R(x)G^R(x)+x^{n-m+1}x^{m-1}R(\frac{1}{x})\\ F^R(x)&\equiv Q^R(x)G^R(x)\;mod\;x^{n-m+1}\\ F^R(x)[G^R(x)]^{-1}&\equiv Q^R(x)\;mod\;x^{n-m+1} \end{aligned} F(x)xnF(x)xnF(x1)FR(x)FR(x)FR(x)[GR(x)]1=Q(x)G(x)+R(x)=xnQ(x)G(x)+xnR(x)=xnmQ(x1)xmG(x1)+xnm+1xm1R(x1)=QR(x)GR(x)+xnm+1xm1R(x1)QR(x)GR(x)modxnm+1QR(x)modxnm+1
现在我们求出了在模 x n − m + 1 x^{n-m+1} xnm+1意义下 Q R ( x ) Q^R(x) QR(x)的解,则
Q R ( x ) = F R ( x ) [ G R ( x ) ] − 1    m o d    x n − m + 1 + a n − m + 1 x n − m + 1 + a n − m + 2 x n − m + 2 + . . . Q^R(x)=F^R(x)[G^R(x)]^{-1}\;mod\;x^{n-m+1}+a_{n-m+1}x^{n-m+1}+a_{n-m+2}x^{n-m+2}+... QR(x)=FR(x)[GR(x)]1modxnm+1+anm+1xnm+1+anm+2xnm+2+...
但又因为 D e g ( G R ) = D e g ( G ) = n − m < n − m + 1 Deg(G^R)=Deg(G)=n-m<n-m+1 Deg(GR)=Deg(G)=nm<nm+1,所以
Q R ( x ) = F R ( x ) [ G R ( x ) ] − 1    m o d    x n − m + 1 Q^R(x)=F^R(x)[G^R(x)]^{-1}\;mod\;x^{n-m+1} QR(x)=FR(x)[GR(x)]1modxnm+1

本文地址:https://blog.csdn.net/qq_43520313/article/details/109248462

相关标签: 多项式