神奇的多项式2 （ln exp Finv Sqrt）

神奇的多项式2

牛顿迭代？

设

$F(G(x))\equiv 0 (\mod x^n)$

$F(G_0(x))\equiv 0 (\mod x^{\frac{n}{2}})$

在$G_0(x)$处泰勒展开 （大学生都会吧）

$$F(G(x))=\sum_{i=0}^{\infty} \frac{F^i(G_0(x))}{i!}(G(x)-G_0(x))^i$$

后面这个考虑$i=2$,$G_0(x)-G(x)$前$\frac{n}{2}$项$=0$，所以一定$(G(x)-G_0(x))^i(\mod x^n)=0$

$$F(G(x))= F(G_0(x))+{F^1(G_0(x))}(G(x)-G_0(x))=0(\mod x^n)\\ G(x)\equiv G_0(x)-\frac{F(G_0(x))}{F^1(G_0(x))}(\mod x^n)$$

$Finv$

$$g(x)f(x)\equiv 1 (\mod x^n)\\$$ $$g_0(x)f(x)\equiv 1 (\mod x^{\frac{n}{2}})\\ f(x)(g(x)-g_0(x))\equiv 0 (\mod x^{\frac{n}{2}})\\ (g(x)-g_0(x))^2\equiv 0(\mod x^{n})\\ g^2(x)+g_0^2(x)-2g(x)g_0(x)\equiv 0(\mod x^{n})\\ f(x)g^2(x)+f(x)g_0^2(x)-f(x)2g(x)g_0(x)\equiv 0(\mod x^{n})\\ g(x)+f(x)g_0^2(x)-2g_0(x)\equiv 0(\mod x^{n})\\ g(x)\equiv 2g_0(x)-f(x)g_0^2(x)(\mod x^{n})\\$$

$Ln$

$$g(x)\equiv \ln f(x) (\mod x^n)\\ g^1(x)\equiv \frac{f^1(x)}{f(x)} (\mod x^n)$$

求出$f(x)$的导数，$f(x)$的逆，积分回去即可。

$EXP$

$$g(x)\equiv e^{f(x)} (\mod x^n)\\ \ln g(x) -f(x)\equiv 0 (\mod x^n)\\ F(g(x))=\ln g(x) -f(x)\\ g(x)\equiv g_0(x)-\frac{\ln g_0(x) -f(x)}{\frac{1}{g_0(x)}}=g_0(x)(1+\ln g_0(x) -f(x))(\mod x^{n})$$

$Sqrt$

$$g^2(x)\equiv f(x) (\mod x^n)\\ g^2(x) -f(x)\equiv 0 (\mod x^n)\\ F(g(x))=g^2(x) -f(x)\\ g(x)\equiv g_0(x)-\frac{g_0^2(x) -f(x)}{2{g_0(x)}}=\frac{g_0^2(x) +f(x)}{2{g_0(x)}}(\mod x^{n})$$

$g(0)=\sqrt{f(0)}$,考虑二次剩余！！