定义
我们说$B(x)$是$A(x)$在模$x^n$意义下的逆元则是满足
$$A(x)\ast B(x)\equiv1(mod \; x^n)$$
分治
考虑分治
假如我们已经知道在模$x^{\lceil \frac{n}{2} \rceil}$下$A$的逆$B’$
即
$$A(x)\ast B’(x)\equiv 1(mod \; x^{\lceil \frac{n}{2} \rceil})$$
$$A(x)\ast B’(x)-1\equiv 0(mod \; x^{\lceil \frac{n}{2} \rceil})$$
两边平方即可得
$$(A(x)\ast B’(x)-1)^2\equiv 0(mod \; x^{2\lceil \frac{n}{2} \rceil})$$
显然$2\lceil \frac{n}{2} \rceil \geq n$
所以
$$(A(x)\ast B’(x)-1)^2\equiv 0(mod \; x^n)$$
$$A^2(x)\ast B’^2(x)-2A(x)\ast B’(x)+1\equiv 0(mod \; x^n)$$
$$2A(x)\ast B’(x)-A^2(x)\ast B’^2(x)\equiv 1(mod \; x^n)$$
$$A(x)(2B’(x)-A(x)\ast B’^2(x))\equiv 1(mod \; x^n)$$
那么$B(x)=2B’(x)-A(x)\ast B’^2(x)$即为满足$A(x)\ast B(x)\equiv 1(mod \; x^n)$的$B(x)$