多项式求逆与多项式开根

闲着没事干研究些黑科技（雾）

多项式求逆

求 A(x)*B(x)==1(mod x^n)

其中n为A(x)，B(x)的度的较大值

已知A(x)求B(x)，B(x)=A(x)^(-1)(mod x^n)

假设n=1，则B(x)=A(x)常数项在mod p 意义下的的逆元

假设n>1

已知 A(x)*B’(x)==1(mod x^(n/2))

A(x)*B(x)==1(mod x^n) ==> A(x)*B(x)==1(mod x^(n/2))

两式相减

A(x)*(B(x)-B’(x))==0(mod x^(n/2))

A(x)显然不全0，否则无解

同除掉A(x)：B(x)-B’(x)==0(mod x^(n/2))

两边同时平方

B(x)^2-2*B(x)*B’(x)+B’(x)^2==0(mod x^n)

两边同乘A(x)

A(x)*B(x)==0(mod n)

所以可化为：B(x)-2*B’(x)+B’(x)^2*A(x)==0(mod x^n)

B(x)=2*B’(x)-B’(x)^2*A(x)(mod x^n)

直接上NTT就好了

从n=1一直往回推，时间复杂度O（n(logn)^2）

多项式开根

求 B(x)*B(x)==A(x)(mod x^n)

如果n==1，直接把A(x)中的常数项搞个二次剩余

对于n>1

考虑 B’(x)^2==A(x)(mod x^(n/2))

同样的思路，把第一个式子变成 B(x)^2==A(x)(mod x^(n/2))

两式相减 (B(x)+B’(x))*(B(x)-B’(x))==0(mod x^(n/2))

可以得到B(x)有两个解，考虑B(x)=B’(x)(mod意义下)

B(x)-B’(x)==0(mod x^(n/2))

两边平方 B(x)^2-2*B(x)*B’(x)+B’(x)^2==0(mod x^n)

将B(x)^2==A(x)(mod x^n)代入

A(x)-2*B(x)*B’(x)+B’(x)^2==0(mod x^n)

B(x)=A(x)+B’(x)^2 / 2*B’(x) (mod x^n)

套多项式求逆和NTT就好了