Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
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,

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 ≤ im, suppose gi(x) = ai0 + ai1x + ai2x2 + ⋯ + aixδi, we define the sequence Si = { ai, ai−1, ai−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, jm 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```

Source

[Submit]   [Go Back]   [Status]   [Discuss]