多项式除法及取模——学习笔记

多项式除法与取模,即 \[ \deg A =n,\ \deg B=m \\ A(x)=D(x)B(x)+R(x) \\ \deg D \le n-m,\ \deg R <m \]

我们需要求 \(D\)\(R\)

我们设 \(A^R(x)=x^{\deg A}A(\frac{1}{x})\) , 即把 \(A\) 系数反转。我们把上面的式子用 \(\frac{1}{x}\) 带入后再乘 \(x^{\deg A}\)\[ x^n A(\frac{1}{x}) = x^nD(\frac{1}{x})B(\frac{1}{x})+x^nR(\frac{1}{x}) \]

\(D\) 看成 \(n-m\) 次, \(R\) 看成\(m-1\) 次 ,得到 \[ A^R(x)=D^R(x)B^R(x) +x^{n-m+1} R^R(x) \\ A^R(x) \equiv D^R(x)B^R(x) \pmod{x^{n-m+1}} \\ \frac{A^R(x)}{B^R(x)} \equiv D^R(x) \pmod{x^{n-m+1}} \]

然后就能求 \(D\) 了,代回去 \(R\) 也就知道了.