发布时间：2024-07-31

多项式除法

给定一个 $n$ 次多项式 $F(x)$ 和一个 $m$ 次多项式 $G(x)$ ，请求出多项式 $Q(x)$ , $R(x)$ ，满足以下条件：

$Q(x)$ 次数为 $n-m$ ， $R(x)$ 次数小于 $m$
$F(x) = Q(x) * G(x) + R(x)$

考虑一种翻转操作， $A_R(x)=x^nA(\frac{1}{x})$ ，即 $A_{n-i}=A_{i}$

$F(\frac{1}{x})=Q(\frac{1}{x})G(\frac{1}{x})+R(\frac{1}{x})$

$x^nF(\frac{1}{x})=x^{n-m}Q(\frac{1}{x}) * x^mG(\frac{1}{x})+x^{n-m+1}*x^{m-1}R(\frac{1}{x})$

$F_R(x)=Q_R(x)G_R(x)+x^{n-m+1}R_R(x)$

$F_R(x) \equiv Q_R(x)G_R(x)(\mod x^{n-m+1})$

$Q_R(x) \equiv F_R(x)G_R^{-1}(x)(\mod x^{n-m+1})$

最后 $R(x)=F(x)-G(x)Q(x)$

cpp

pair<poly,poly> div(const poly &f,const poly &g){
    int n=f.size(),m=g.size(),len=n-m+1;
    poly fr=reverse(f,n),gr=reverse(g,m);
    gr.resize(len);
    for(int i=len;i<m;i++)gr[i]=0;
    gr=inv(gr,len);
    poly q=mul(fr,gr,n,len);
    q=reverse(q,len);
    poly r=sub(f,mul(q,g,len,m));
    return {q,r};
}
void solve(){
    int n,m;
    cin>>n>>m;
    poly f(n+1),g(m+1);
    for(int i=0;i<=n;i++)cin>>f[i];
    for(int i=0;i<=m;i++)cin>>g[i];
    auto [q,r]=div(f,g);
    for(int i=0;i<=n-m;i++)cout<<q[i]<<" \n"[i==n-m];
    for(int i=0;i<m;i++)cout<<r[i]<<" \n"[i==m-1];
}

多项式除法 ​

多项式除法