题解 P5277 【【模板】多项式开根（加强版）】

· · 题解

给一个方法，开多少次方都可以。当然对于这道题只要写一个开方就可以了。

根据初中数学只是可以知道:

\sqrt[k] a=a^{\frac{1}{k}}

那么，我们实际上需要求的是 \frac{1}{k} 次方根。

而在膜意义下，这个数字等价于 a^{k^{-1}} 。

那么，我们就只需要求一个 k^{-1} 次方根就可以了。

如果用分治乘法的话， k 可能不与 mod-1 互质， k^{-1} 可能不存在。但是一般情况下， k 与 mod 是互质的。因此我们只需要套用 \ln 和 \exp 实现的快速幂即可。

复杂度为 O(n\log n) 。

这里给一个求 k 次剩余的方法。

可以知道，我们平常用的膜数都是 998244353 之类的膜数，因此原根一般是有完整定义的。

那么，设 a_0=3^t ，我们需要的其实是 3^{\frac{t}{k}} 。

如果 \frac{t}{k} 在膜 mod-1 意义下不存在，那么这个数字不存在 k 次剩余。

否则我们直接用 exgcd 算出结果就可以了。利用 BSGS 实现求 t ，复杂度为 O(\sqrt{mod}) 。

核心代码:

int dir=0,fst;

map<int,int>G;

const int iv2=(mod+1)/2;

inline int gettwo(int x)//用BSGS求二次剩余
{
    const int blk=sqrt(mod);
    register int z=1,t=1;
    rep(i,0,blk)G[z]=i,z=z*3ll%mod;
    z=power(z,mod-2);
    for(register int i=0;;++i)
    {
        if(G[(ll)x*t%mod])
        {
            int mz=i*blk+G[(ll)x*t%mod];
            return power(3,mz/2);
        }//只要二次方根，不需要exgcd。
        t=(ll)t*z%mod;
    }
    return x;
}

int main()
{
    if(!F[0])
    {
        dir=-1;
        Rep(i,1,n)if(F[i]){dir=i;break;}
        if(dir==-1){Rep(i,1,n)write(0,' ');flush();exit(0);}
        Rep(i,dir,n)F[i-dir]=F[i],F[i]=0;
    }
    fst=F[0];
    register int iv=power(fst,mod-2);
    Rep(i,0,n)F[i]=(ll)F[i]*iv%mod;
    Ln(F,F,n);
    Rep(i,0,n)F[i]=(ll)F[i]*iv2%mod;//直接上 ln 和 exp
    Exp(F,F,n);
    fst=gettwo(fst);
    if(fst>(mod+1)/2)fst=mod-fst;
    Rep(i,1,dir/2)write(0,' ');
    Rep(i,0,n-dir/2)write((ll)fst*F[i]%mod,' ');
    return 0;
}