牛顿迭代求逆元

适用于 \(\bmod p^k\) 这样的东西，和多项式求逆一样的

\[x \times A \equiv 1 \mod p^k\\ x \times B \equiv 1 \mod p^{2k}\\ (B-A)^2 \equiv 0 \mod p^{2k}\\ B^2-2AB+A^2 \equiv 0 \mod p^{2k}\\ B-2A+A^2\times x \equiv 0 \mod p^{2k}\\ B=A(2-A\times x) \mod p^{2k}\\ \]

泰勒展开可以得到同样的
结果。

\[F(x)=\frac 1{x} -A\\ x = x_0+\frac{\frac 1{x_0}-A}{\frac 1 {x_0^2}}=2x_0-A\times x_0^2 \]