3584 -- Small Polynomial Factorization

Language:

Small Polynomial Factorization

Time Limit: 10000MS		Memory Limit: 65536K
Total Submissions: 317		Accepted: 64
Case Time Limit: 5000MS

Description

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.

Input

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

f(x) = a₀ + a₁x + a₂x² + ⋯ + 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) = 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δ_i}x^δ_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.

Output the factorization using the following format:

a₀₀
a₁₀	a₁₁	⋯	a_1δ₁
a₂₀	a₂₁	⋯	a_2δ₂
⋮	⋮
a_m0	a_m1	⋯	a_{mδ_m}

Sample Input

36 -30 -2 4

Sample Output

Source

POJ Founder Monthly Contest – 2008.04.13, frkstyc