多项式开根

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


Description

给定多项式 ,求 ,满足:

Methods

倍增法

假设现在已经求出了 在模 意义下的平方根 ,则有:

倍增计算即可。

时间复杂度

还有一种常数较小的写法就是在倍增维护 的时候同时维护 而不是每次都求逆。

时,可能需要使用二次剩余来计算

Newton's Method

参见 Newton's Method .

Examples

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


Copyright © 2016 - 2020 OI Wiki Team

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

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