多项式除法|取模
描述
给定多项式 ,求 除 的商 和余数 。
解法
发现若能消除 的影响则可直接 多项式求逆 解决。
考虑构造变换
观察可知其实质为反转 的系数。
设 。
将 中的 替换成 并将其两边都乘上 ,得到:
注意到上式中 的系数为 ,则将其放到模 意义下即可消除 带来的影响。
又因 的次数为 ,故 不会受到影响。
则:
使用多项式求逆即可求出 ,将其反代即可得到 。
时间复杂度 。
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用