多项式取模及其应用

2019-04-13 13:00发布

站内文章 / 模拟电子
11859 0 1602

前置知识

多项式求逆。

多项式取模

问题描述

求A(x) mod B(x)，其中degA>=degB

Solution

令A(x)=B(x)C(x)+D(x)，其中degD<degB
设degA=n，degB=m，则degD <m，degC< n-m+1 有A(1x)=B(1x)C(1x)+D(1x) 两边同时乘上xn，可得 xnA(1x)=xmB(1x)xn−mC(1x)+xnD(1x) 考虑一下这个式子是什么意思，其实就是将系数全部对称交换一次，
即[x0]A(x)=[xn]xnA(1x)，[x1]A(x)=[xn−1]xnA(1x)…… 接下来考虑每一个新得到的多项式的指数的范围。
xnA(1x)的每一项指数范围为[0,n]
xmB(1x)的每一项指数范围为[0,m]
xn−mC(1x)的每一项指数范围为

热门文章