多项式开根

Description

给定多项式 ，求 ，满足：

Methods

倍增法

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

倍增计算即可。

时间复杂度

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

当 时，可能需要使用二次剩余来计算 。

Newton's Method

参见

Newton's Method .

Examples

1. 「Codeforces Round #250」E. The Child and Binary Tree