Welcome to ZOJ
Select Problem
ZOJ Problem Set - 1640
Integer Roots of a Polynomial

Time Limit: 2 Seconds      Memory Limit: 65536 KB

A polynomial of degree n has the common form as

p(x) = a[n]*x^n + a[n-1]*x^(n-1) + ... + a[1]*x + a[0].

In general it is difficult to find the roots of a polynomial of degree 3 or higher, unless you have a powerful computer program available. The following observation might be helpful:

Let p(x) be a polynomial with integer coefficients. If p(c) = 0 for some integer c, then (x - c) is a factor of p(x) and c is a divisor of the constant term of p(x).

Your task is to write a program to find all the integer roots of a given polynomial with integer coefficients.


The first line of input contains a positive integer N (N <= 100), then followed by N test cases. Each test case consists of 2 lines of integers: the first line contains a non-negative integer n (n <= 20) which is the degree of the polynomial; and the second line contains n+1 integers a[n], a[n-1], ..., a[1], and a[0]. Note that 0-polynomial will not appear in the input.


For each test case, print in one line all the integer roots of the given polynomial in ascending order. The roots must be separated by one space. If there is no integer root at all, just print "NIR" (means No Integer Root).

Sample Input

-1 18 -96 160
1 0 1
2 3 0

Sample Output

4 4 10

Author: CHEN, Yue
Source: Zhejiang University Local Contest 2003
Submit    Status