[F(x)=Q(x)G(x)+R(x) ]
已知(n)次的(F(x))和(m)次(G(x))求商(Q(x))和余数(R(x))，要求(Q(x))次数为(n-m)，(R(x))次数小于(m)
以下(inv(x))表示(x)的逆元
首先考虑整除的情况
[Q=F*inv(G) ]
所以考虑通过构造消除掉(R)
[f^r(x)=x^{\deg f}f\left(\frac 1 x\right) ]
[F^r(x)=Q^r(x)G^r(x)+x^{n-m+1}R^r(x) ]
由于(Q^r)的最高次项为(n-m)小于(n-m+1)，有
[F^r(x)\equiv Q^r(x)G^r(x)\pmod {x^{n-m+1}} ]
再带入(Q(x))可求出(R(x))
可以发现
[f(x)=f_0+f_1x+f_2x^2\dots\ f^r(x)=f_n+f_{n-1}x+f_{n-2}x^2\dots ]
(f^r)和(f)可以(O(n))的互推
复杂度就是求逆和乘的(O(n\log n))
Original: https://www.cnblogs.com/29taorz/p/15736942.html
Author: T_X蒻
Title: 多项式除和取余
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/644053/
转载文章受原作者版权保护。转载请注明原作者出处！