多项式除法及取模 介绍 首先你需要会多项式求逆,可参考另一篇博文。 多项式除法和多项式取模有很多应用,比如线性递推的优化,多项式多点求值和多点插值。 基本概念 对于一个多项式 A(x)A(x)A(x) ,称其最高项的次数为 A(x)A(x)A(x) 的度 ,记作 degAdegAdegA 。 对于多项式 A(x),B(x)A(x),B(x)A(x),B(x) ,存在唯一的 Q(x),R(x)Q(x),R(x)Q(x),R(x) 满足 A(x)=Q(x)B(x)+R(x)A(x)=Q(x)B(x)+R(x)A(x)=Q(x)B(x)+R(x) ,且...