多项式除法

· · 个人记录

多项式除法

定义

f$ 为 $n$ 次多项式，$g$ 为 $m$ 次多项式，$q$ 为 $n-m$ 次多项式，$r$ 的次数 $<m

则 f=g\times q+r，q 为 f 除以 g，r 为余数

求法

设 f_R 为多项式 f 每项的系数反过来写

即 f_R(i)=x^i f(\frac 1 i),f_R(i)=f(n-i)

f=g\times q+r f(\frac 1 x)=g(\frac 1 x)\times q(\frac 1 x)+r(\frac 1 x) x^nf(\frac 1 x)=x^mg(\frac 1 x)\times x^{n-m}q(\frac 1 x)+x^{m-1}r(\frac 1 x)\cdot x^{n-m+1} f_R(x)=g_R(x)\times q_R(x)+r_R(x)\cdot x^{n-m+1}

为了把 r_R 给消去，先求出 q，

f_R(x)\equiv g_R(x)\times q_R(x)+r_R(x)\cdot x^{n-m+1}(\bmod\ x^{n-m+1}) f_R(x)\equiv g_R(x)\times q_R(x)(\bmod\ x^{n-m+1}) q_R(x)\equiv f_R(x)\times g_R(x)^{-1}(\bmod\ x^{n-m+1})

求出 g 的逆，求出 q，再求出 r=f-g\times q

代码

void mul(ll *f, ll *g, ll *h, ll n) // f*g=h
{
    for(lim = 1; lim <= n; lim <<= 1);
    ntt(f, lim, 1), ntt(g, lim, 1);
    for(ll i = 0; i < lim; ++i) h[i] = f[i] * g[i] % mod;
    ntt(h, lim, -1), inv = qmi(lim, mod - 2);
    for(ll i = 0; i <= n; ++i)  h[i] = h[i] * inv % mod;
}
void polymod(ll *f, ll *g, ll *r, ll n, ll m) // f mod g = r,f/g=ar
{
    for(ll i = 0; i <= n; ++i)  ar[i] = f[n - i];
    for(ll i = 0; i <= m; ++i)  br[i] = g[m - i];
    polyinv(br, invb, n - m + 1);
    mul(ar, invb, n, n - m);
    reverse(ar, ar + n - m + 1);
    mul(ar, g, n - m, m);
    for(ll i = 0; i < m; ++i)   r[i] = add(f[i], mod - ar[i]);
    for(ll i = m; i <= n; ++i)  r[i] = 0;
}

应用

也是多项式运算的基本操作

可以用来优化高精度除法