PP and TMT are mathematics lovers. They like to find and solve interesting mathematic problems together. One day, they found that the polynomial “x^n-1” can be factorized into a large number of long polynomials, although the polynomial “x^n-1” looks simple. They were interested in how to factorize it into irreducible polynomials.
By “irreducible” we mean that it has co-prime coefficients and cannot be further factorized.
Now your task is to help PP and TMT to factorize x^n-1 into several irreducible polynomials over the integers.
The input consists of multiple test cases.
For each test case, there is one line containing only one integer N. (2<=N<=1001)
End of input is indicated by a line containing a zero.
For each test case, output the factorization of the given polynomial according to the writing habit, i.e. x5, 5x2, 3x, x2-x.
There are multiple ways to express the factorization of a polynomial. To make it unique, we sort the irreducible polynomials according to the following rules:
Lower order polynomials are always lexicographically smaller than higher order polynomials. Same order polynomials should be sorted by their coefficients. We compare the coefficients from high degree terms to low degree terms, including the omitted terms, which the coefficients are regard as 0. Coefficients are being compared first by absolute value then by sign. Smaller absolute values are lexicographically smaller. For the same absolute value, negative coefficients are lexicographically smaller than positive coefficients.
2 3 4 5 6 12 256 0
(x-1)(x+1) (x-1)(x^2+x+1) (x-1)(x+1)(x^2+1) (x-1)(x^4+x^3+x^2+x+1) (x-1)(x+1)(x^2-x+1)(x^2+x+1) (x-1)(x+1)(x^2+1)(x^2-x+1)(x^2+x+1)(x^4-x^2+1) (x-1)(x+1)(x^2+1)(x^4+1)(x^8+1)(x^16+1)(x^32+1)(x^64+1)(x^128+1)
Migrated from old NTUJ.
2009 ACM/ICPC Shanghai Invitational Contest
| No. | Testdata Range | Score |
|---|