Small Polynomial Factorization

Time Limit
10s
Memory Limit
65536KB
Judge Program
Standard
Ratio(Solve/Submit)
0.00%(0/0)
Description:

Given a polynomial over the integers, for instance,

4x3 − 2x2 − 30x + 36,

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

4x3 − 2x2 − 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.

Input:

The input consists of multiple test cases. Each test case occupies one line which contains δ + 1 (0 ≤ δ ≤ 10) integers a0, a1, …, aδ such that |ai| ≤ 1000, ∀i : 0 ≤ i ≤ δ. These integers define a polynomial

f(x) = a0 + a1x + a2x2 + ⋯ + aδxδ,

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

Output:

For each test case, output the factorization of the given polynomial. There are multiple ways to express the factorization of a polynomial. To make it unique, we require that f(x) be factorized into

f(x) = g0(x)g1(x)g2(x)⋯gm(x),

where g0(x) shall always be an integer and not be omitted even if it is 1; g1(x), g2(x), …, gm(x) are irreducible polynomials whose highest-order terms have positive coefficients. For each i such that 0 ≤ i ≤ m, suppose gi(x) = ai0 + ai1x + ai2x2 + ⋯ + aiδixδi, we define the sequence Si = { aiδi, aiδi−1, aiδi−2, …, ai0 }. Using the Si, we place the following constraints on the ordering of g1(x), g2(x), …, gm(x):

For any i, j such that 0 ≤ i, j ≤ m and gi(x) ≠ gj(x),

  • if δi < δj, gi(x) shall precede gj(x);
  • if δi = δj, gi(x) shall precede gj(x) iff Si is lexicographically smaller than Sj, elements being compared first by their magnitudes then by their values.
Output the factorization using the following format:
a00



a10 a11 ⋯ a1δ1
a20 a21 ⋯ a2δ2
⋮
⋮


am0 am1 ⋯ amδm

Sample Input:
36 -30 -2 4
Sample Output:
2
-2 1
3 1
-3 2
Submit