Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Small Polynomial Factorization
Time Limit: 10000MSMemory Limit: 65536K
Total Submissions: 257Accepted: 62
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

Sample Input

36 -30 -2 4

Sample Output

2
-2 1
3 1
-3 2

Source

[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