Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Small Polynomial Factorization
Time Limit: 10000MSMemory Limit: 65536K
Total Submissions: 317Accepted: 64
Case Time Limit: 5000MS


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.


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.


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:

a10 a11 a1δ1
a20 a21 a2δ2

am0 am1 am

Sample Input

36 -30 -2 4

Sample Output

-2 1
3 1
-3 2


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

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator