F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Factorization

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 250    Accepted Submission(s): 71


Problem Description
LMY and YY 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 LMY and YY to factorize x^n-1 into several irreducible polynomials over the integers.
 

Input
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.
 

Output
For each test case, output the factorization of the given polynomial according to the writing habit, i.e. x^5, 5x^2, 3x, x^2-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.
 

Sample Input
2 3 4 5 6 12 256 0
 

Sample Output
(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)
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-25 17:06:55, Gzip enabled