多項式求逆與多項式開根

閑着沒事幹研究些黑科技（霧）

多項式求逆

求 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就好了