c2c网站管理系统,建湖人才网招工,做一个网页需要什么,昆明网站建设设计牛顿迭代法
定义
在一般意义下#xff0c;牛顿迭代法可以求出一个函数的零点#xff0c;而在多项式意义下#xff0c;牛顿迭代能够求出#xff1a;给定一个G(x)G(x)G(x)#xff0c;求F(x)F(x)F(x)#xff0c;使得G(F(x))≡0(modxn)G(F(x)) \equiv 0\;\;\;(mod\;\;x^n)G…牛顿迭代法
定义
在一般意义下牛顿迭代法可以求出一个函数的零点而在多项式意义下牛顿迭代能够求出给定一个G(x)G(x)G(x)求F(x)F(x)F(x)使得G(F(x))≡0(modxn)G(F(x)) \equiv 0\;\;\;(mod\;\;x^n)G(F(x))≡0(modxn)
推导
当n1n1n1时单独求解F(x)F(x)F(x)的值。 当n1n1n1时假设我们已经求出了F0(x)F_0(x)F0(x)满足G(F0(x))0(modx⌈n2⌉)G(F_0(x))0\;\;\;(mod\;\;x^{\lceil \frac{n}{2} \rceil})G(F0(x))0(modx⌈2n⌉)。
考虑如何用F0(x)F_0(x)F0(x)求出F(x)F(x)F(x)。 将G(F(x))G(F(x))G(F(x))在F0(x)F_0(x)F0(x)处泰勒展开。 G(F(x))G(F0(x))G(F0′(x))1!(F(x)−F0(x))G(F0′′(x))2!(F(x)−F0(x))……G(F(x))G(F_0(x))\frac{G(F_0(x))}{1!}(F(x)-F_0(x))\frac{G(F_0(x))}{2!}(F(x)-F_0(x))…… G(F(x))G(F0(x))1!G(F0′(x))(F(x)−F0(x))2!G(F0′′(x))(F(x)−F0(x))…… 可以发现F(x)−F0(x)F(x)-F_0(x)F(x)−F0(x)的非零项大于⌈n2⌉\lceil \frac{n}{2} \rceil⌈2n⌉因此有(F(x)−F0(x))2(F(x)-F_0(x))^2(F(x)−F0(x))2的非零项大于nnn所以有 G(F(x))G(F0(x))G(F0′(x))(F(x)−F0(x))(modxn)G(F(x))G(F_0(x))G(F_0(x))(F(x)-F_0(x))\;\;\;(mod\;\;x^n) G(F(x))G(F0(x))G(F0′(x))(F(x)−F0(x))(modxn)
因为G(F(x))≡0(modxn)G(F(x)) \equiv 0\;\;\;(mod\;\;x^n)G(F(x))≡0(modxn)所以 F(x)F0(x)−G(F0(x))G(F0′(x))F(x)F_0(x)-\frac{G(F_0(x))}{G(F_0(x))} F(x)F0(x)−G(F0′(x))G(F0(x))
应用
多项式求逆
已知多项式A(x)A(x)A(x)求一个多项式F(x)F(x)F(x)使得F(x)A(x)≡1(modxn)F(x)A(x)\equiv 1\;\;\;(mod\;\;x^n)F(x)A(x)≡1(modxn)。 相当于求F(x)F(x)F(x)满足A(x)−1F(x)≡0(modxn)A(x)-\frac{1}{F(x)}\equiv 0\;\;\;(mod\;\;x^n)A(x)−F(x)1≡0(modxn)
令G(x)A(x)−1F0(x)G(x)A(x)-\frac{1}{F_0(x)}G(x)A(x)−F0(x)1 则根据牛顿迭代有 F(x)F0(x)−A(x)−1F0(x)F0(x)−2(modxn)F(x)F_0(x)-\frac{A(x)-\frac{1}{F_0(x)}}{F_0(x)^{-2}}\;\;\;(mod\;\;x^n) F(x)F0(x)−F0(x)−2A(x)−F0(x)1(modxn) 因此有 F(x)F0(x)(2−F0(x)A(x))(modxn)F(x)F_0(x)(2-F_0(x)A(x))\;\;\;(mod\;\;x^n) F(x)F0(x)(2−F0(x)A(x))(modxn) 因此递归求解F0(x)F_0(x)F0(x)即可感觉比倍增法的推导精妙一些虽然求逆的倍增法和牛顿迭代的推法差不多。
多项式开方
已知多项式A(x)A(x)A(x)求一个多项式F(x)F(x)F(x)使得F(x)2≡A(x)(modxn)F(x)^2\equiv A(x)\;\;\;(mod\;\;x^n)F(x)2≡A(x)(modxn)。
相当于求F(x)F(x)F(x)满足F(x)2−A(x)≡0(modxn)F(x)^2-A(x)\equiv 0\;\;\;(mod\;\;x^n)F(x)2−A(x)≡0(modxn)
令G(x)F0(x)2−A(x)G(x)F_0(x)^2-A(x)G(x)F0(x)2−A(x)。 F(x)F0(x)−F0(x)2−A(x)2F0(x)F(x)F_0(x)-\frac{F_0(x)^2-A(x)}{2F_0(x)} F(x)F0(x)−2F0(x)F0(x)2−A(x) 因此 F(x)F0(x)A(x)2F0(x)(modxn)F(x)\frac{F_0(x)A(x)}{2F_0(x)}\;\;\;(mod\;\;x^n) F(x)2F0(x)F0(x)A(x)(modxn) 时间复杂度O(nlgn)O(nlgn)O(nlgn)在A(0)1A(0)1A(0)1时常数项为111否则还需要二次剩余计算。
多项式exp
已知多项式A(x)A(x)A(x)求一个多项式F(x)F(x)F(x)使得F(x)eA(x)(modxn)F(x)e^{A(x)}\;\;\;(mod\;\;x^n)F(x)eA(x)(modxn)。
相当于求F(x)F(x)F(x)满足lnF(x)≡A(x)(modxn)\ln F(x)\equiv A(x)\;\;\;(mod\;\;x^n)lnF(x)≡A(x)(modxn)
令G(x)lnF0(x)−A(x)G(x)\ln F_0(x)-A(x)G(x)lnF0(x)−A(x)。
把F0(x)F_0(x)F0(x)当做一个常量因此 F(x)F0(x)−lnF0(x)−A(x)1F0(x)F(x)F_0(x)-\frac{lnF_0(x)-A(x)}{\frac{1}{F_0(x)}} F(x)F0(x)−F0(x)1lnF0(x)−A(x) 即 F(x)F0(x)(1−lnF0(x)A(x))F(x)F_0(x)(1-\ln F_0(x)A(x)) F(x)F0(x)(1−lnF0(x)A(x)) 时间复杂度O(nlgn)O(nlgn)O(nlgn)A(0)0A(0)0A(0)0时F(0)1F(0)1F(0)1。
多项式k次幂
已知多项式A(x)A(x)A(x)以及一个整数kkk求一个多项式F(x)F(x)F(x)使得F(x)A(x)k(modxn)F(x)A(x)^k\;\;\;(mod\;\;x^n)F(x)A(x)k(modxn)。
相当于求F(x)F(x)F(x)满足lnF(x)−klnA(x)≡0(modxn)\ln F(x)-k\ln A(x)\equiv 0\;\;\;(mod\;\;x^n)lnF(x)−klnA(x)≡0(modxn) 也就是F(x)−eklnA(x)≡0(modxn)F(x)-e^{k\ln A(x)}\equiv 0\;\;\;(mod\;\;x^n)F(x)−eklnA(x)≡0(modxn)
因此先ln\lnln再乘kkk再expexpexp回去即可。
时间复杂度O(nlgn)O(nlgn)O(nlgn)。
Code详见多项式全家桶