多项式开方

描述

给定多项式 ，求 ，满足：

解法

倍增法

首先讨论 不为 的情况。

易知：

若 没有平方根，则多项式 没有平方根。

可能有多个平方根，选取不同的根会求出不同的 。

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

倍增计算即可。

时间复杂度

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

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

上述方法需要知道 的逆，所以常数项不能为 。

若 ，则将 分解成 ，其中 。

• 若 是奇数，则 没有平方根。

• 若 是偶数，则求出 的平方根 ，然后得到 。

Newton's Method

参见

Newton's Method.

例题

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