3584：Small Polynomial Factorization

Given a polynomial over the integers, for instance,

4x³ − 2x² − 30x + 36,

we can factorize it into several irreducible polynomials over the integers, i.e.

4x³ − 2x² − 30x + 36 = 2(x − 2)(x + 3)(2x − 3).

By “irreducible” we mean that it has coprime coefficients and cannot be further factorized.

Write a program that is capable of factorizing polynomials of order at most 10 and with integral coefficients not exceeding 1000 by magnitude.

f(x) = a₀ + a₁x + a₂x² + ⋯ + a_δx^δ,

which is to be factorized. The input ends once EOF is met.

f(x) = g₀(x)g₁(x)g₂(x)⋯g_m(x),

where g₀(x) shall always be an integer and not be omitted even if it is 1; g₁(x), g₂(x), …, g_m(x) are irreducible polynomials whose highest-order terms have positive coefficients. For each i such that 0 ≤ i ≤ m, suppose g_i(x) = a_i0 + a_i1x + a_i2x² + ⋯ + a_iδix^δ_i, we define the sequence S_i = { a_iδi, a_iδi−1, a_iδi−2, …, a_i0 }. Using the S_i, we place the following constraints on the ordering of g₁(x), g₂(x), …, g_m(x):

For any i, j such that 0 ≤ i, j ≤ m and g_i(x) ≠ g_j(x),

• if δ_i < δ_j, g_i(x) shall precede g_j(x);
• if δ_i = δ_j, g_i(x) shall precede g_j(x) iff S_i is lexicographically smaller than S_j, elements being compared first by their magnitudes then by their values.