多项式开根
模板题：Luogu P5205、Luogu P5277。
特殊情况：$a_0=1$
即 Luogu P5205。
牛顿法
推导过程
设
$$H^2(x) \equiv F(x) \pmod {x^{\lceil \frac{n}{2} \rceil}}$$
$$G(x) \equiv H(x) \pmod {x^{\lceil \frac{n}{2} \rceil}}$$
$$G(x)-H(x) \equiv 0 \pmod {x^{\lceil \frac{n}{2} \rceil}}$$
$$(G(x)-H(x))^2 \equiv 0 \pmod {x^n}$$
$$G^2(x)-2H(x) \times G(x)+H^2(x) \equiv 0 \pmod {x^n}$$
$$F(x)-2H(x) \times G(x)+H^2(x) \equiv 0 \pmod {x^n}$$
$$G(x)=\dfrac{F(x)+H^2(x)}{2H(x)}$$
对上述式子进行多项式求逆 + NTT 即可。
代码实现
迭代版
高级封装迭代版
一般情况
即 Luogu P5277。
套上奇素数模数的二次剩余模板（Cipolla 算法）即可。