Polynomial Arithmetic

The operations and their costs

Operation	Naive	Fast	Method
Add / subtract	$O(n)$	$O(n)$	coefficientwise
Scalar multiply	$O(n)$	$O(n)$
Multiply	$O(n^2)$	$O(n\log n)$	FFT/NTT
Divide by $(x-a)$	$O(n)$	$O(n)$	synthetic division
Divide with remainder	$O(n^2)$	$O(n\log n)$	Newton on the reversed polynomial
Evaluate at one point	$O(n)$	$O(n)$	Horner
Evaluate at $n$ points	$O(n^2)$	$O(n{\log }^{2}n)$	multipoint evaluation
Interpolate from $n$ points	$O(n^2)$	$O(n{\log }^{2}n)$	inverse multipoint
Derivative / integral	$O(n)$	$O(n)$	coefficientwise
GCD	$O(n^2)$	$O(n{\log }^{2}n)$	half-GCD
Composition $A(B(x))$	$O(n^2)$	$O(n{\log }^{2}n)$	Brent-Kung
Power $A^k$	$O(nk)$	$O(n\log n)$	$\exp (k\log A)$
Shift $A(x+c)$	$O(n^2)$	$O(n\log n)$	a convolution with binomials

Horner’s method

long long evaluate(const vector<long long>& a, long long x, long long MOD) {
    long long res = 0;
    for (int i = a.size() - 1; i >= 0; i--) res = (res * x + a[i]) % MOD;
    return res;
}

$n$ multiplications and $n$ additions — optimal for a single evaluation, and the standard way to compute a polynomial hash.

Division with remainder

$A=QB+R$ with $\mathrm{deg}R<\mathrm{deg}B$. Naive long division is $O(n^2)$; the fast version uses the reversal trick:

$\mathrm{rev}(A)\equiv \mathrm{rev}(B)\cdot \mathrm{rev}(Q)(\mathrm{mod}{x}^{\mathrm{deg}A-\mathrm{deg}B+1}),$

so $\mathrm{rev}(Q)=\mathrm{rev}(A)\cdot \mathrm{rev}(B{)}^{-1}$ computed as a power series inverse — $O(n\log n)$. Then $R=A-QB$.

// rev(P)[i] = P[deg - i]
pair<Poly,Poly> divmod(Poly a, Poly b) {
    int d = a.size() - b.size();
    if (d < 0) return {{0}, a};
    Poly ra = reversed(a), rb = reversed(b);
    Poly q = reversed(mulTrunc(ra, inverse(rb, d + 1), d + 1));
    Poly r = sub(a, mul(q, b));
    r.resize(b.size() - 1);
    return {q, r};
}

Synthetic division by $(x-a)$

// divide by (x - a); returns the quotient, and the remainder is P(a)
vector<long long> synthetic(vector<long long> p, long long a, long long MOD) {
    for (int i = p.size() - 2; i >= 0; i--)
        p[i] = (p[i] + a * p[i+1]) % MOD;
    long long rem = p[0];
    p.erase(p.begin());
    return p;                                    // remainder = rem = P(a)
}

$O(n)$, and it is the same recurrence as Horner — evaluation and division by a linear factor are the same computation.

Roots and factorisation

Task	Method
Rational roots over $\mathbb{Z}$	rational root theorem: $p\mid a_0$, $q\mid a_n$
Roots modulo a prime	$\gcd (f,x^p-x)$, then Cantor-Zassenhaus
Real roots	Sturm sequences + bisection
All complex roots	Durand-Kerner, or companion-matrix eigenvalues
Squarefree part	$f/\gcd (f,f^{\prime })$
Full factorisation over ${\mathbb{F}}_p$	SFF → DDF → EDF
Factorisation over $\mathbb{Z}$	factor mod $p$, Hensel lift, recombine

Useful identities

$\mathrm{deg}(AB)=\mathrm{deg}A+\mathrm{deg}B,(AB{)}^{\prime }=A^{\prime }B+A{B}^{\prime }$

$A(x)\mathrm{mod}(x-a)=A(a)\text{(the remainder theorem)}$

${\prod }_i(x-r_i)\text{ has coefficients}=\pm \text{elementary symmetric polynomials of the }{r}_i$

The last one (Vieta’s formulas) converts between roots and coefficients, and the product $\prod (x-r_i)$ is computable in $O(n{\log }^{2}n)$ by divide and conquer — the same recursion used for multipoint evaluation.

// product of (x - r_i) in O(n log^2 n)
Poly buildProduct(int lo, int hi) {
    if (hi - lo == 1) return {MOD - r[lo], 1};
    int mid = (lo + hi) / 2;
    return mul(buildProduct(lo, mid), buildProduct(mid, hi));
}

Representation

For contest use, a vector<long long> with index = degree (little-endian) is the right choice: addition is a loop, multiplication feeds straight into NTT, and the derivative is a shift.

Trim trailing zeros after every operation, or the degree bookkeeping drifts.

See also: FFT and NTT · Formal Power Series · Lagrange Interpolation