多项式除法 | 取模

本页面最后更新于: 2020/09/25


Description

给定多项式 ,求 的商 和余数

Method

发现若能消除 的影响则可直接 多项式求逆 解决。

考虑构造变换

观察可知其实质为反转 的系数。

中的 替换成 并将其两边都乘上 ,得到:

注意到上式中 的系数为 ,则将其放到模 意义下即可消除 带来的影响。

又因 的次数为 ,故 不会受到影响。

则:

使用多项式求逆即可求出 ,将其反代即可得到

时间复杂度

本页面最近更新:2020/09/25更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面的全部内容在 CC BY-SA 4.0 SATA 协议之条款下提供,附加条款亦可能应用
0 条评论
未登录用户


Copyright © 2016 - 2020 OI Wiki Team

最近更新: c4f7a45, 2020-09-25

联系方式:Telegram 群组 / QQ 群组