Factoring a Polynomial

Factoring a Polynomial

Problem Description
Let Z[x] be the set of all polynomials in x with integer coefficients. Let f(x) = anx^n + an-1x^n-1 + ... + a1x + a0 be a polynomial in Z[x]. If an is not zero、then the degree of f(x) is n、and an is called the leading coefficients of f(x).
A polynomial f(x) in Z[x] is composite if there are polynomials g(x) and h(x) in Z[x]、with degree at least 1、such that f(x) = g(x)h(x). We call g(x) and h(x) the factors of f(x).
A polynomial is prime if it is not composite. Given a polynomial f(x) with degree at most3、find its prime factors.

Input Format
Input data contains a set of polynomials of degree at most 3. Each polynomial f(x) =
a3x^3 + a2x^2 + a1x + a0 is represented by its coefficients a3、a2、a1、and a0. Assume that the absolute values of all the coefficients are no more than 10000. The last polynomial is followed by 0、0、0、0、indicating the end of input data.

Output Format
For each polynomial f(x)、print its prime factors. When the greatest common divisor of the coefficients is not 1、print the greatest common divisor before its prime factors. It is also required that the leading coefficient of each prime factor is positive.

Sample Input
0 1 2 1
0 -2 4 2
-1 3 -3 1
0 0 0 0

Sample Output
(x + 1)(x + 1)
-2(x^2 - 2x - 1)
-1(x + 1)(x + 1)(x + 1)

解題原理：
1. 以整數陣列讀入係數後進行處理，一個陣列元素依序表示一個係數
2. 判斷最高係數領導次方，並修正為正數係數
3. 提出可能的公因數
4. 使用一次因式檢定排列組合所有可能因式
a3x^3 + a2x^2 + a1x + a0
若 px-q 為一根，則 p a3、q a0
5. 代入可能根計算原式 = 0 表示確有此根，表所有除非重新計算原式
6. 重複計算所有可能根

困難度：***

程式下載

原碼下載

參考來源：中山大學 九十二學年度電腦程式設計競賽 試題 Problem 1