Polynomial Madness

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 0.6s
Python 1.8s
Memory limit: 64M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Konajya is learning how to factor polynomials. Her homework assignment consists of N polynomials which she must factor. The i-th polynomial has degree D_i. Each polynomial is described by a sequence of D_i+1 integers which are the coefficients of the polynomial (i.e. x^2 + 3x + 9 would be given in the format of 1 3 9). Luckily, you know that each polynomial only has real integer roots. Because she is too lazy to factor them by herself, she decided to give this problem to you, so you can do it for her!


1 \le N \le 10\,000
2 \le D_i \le 7
All roots are integers whose absolute value is less than or equal to 150.
The polynomial evaluated at x where -150\le x \le 150 will always yield an absolute value less than 2^{63}-1.

Subtask 1 [5%]

N \le 20

Subtask 2 [10%]

N \le 300

Subtask 3 [25%]

N \le 2000

Subtask 4 [60%]

No additional constraints

Input Specification

On the first line, there is one integer, N, the number of polynomials to follow.
The next N lines contain an integer D representing the degree of the polynomial, followed by D+1 space-separated integers, the coefficients of the polynomial starting from the highest degree to the lowest degree.

Output Specification

Output a total of N lines.
Line i should contain the roots of the i-th polynomial in the input in increasing order. It is guaranteed that the polynomial has D_i integer roots. You are to print the multiple roots.

Sample Input

2 2 -6 4
2 1 6 9
2 1 0 -9

Sample Output

1 2
-3 -3
-3 3


There are no comments at the moment.