Integer Roots of a Polynomial

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.

Input

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.

Output

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

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

Sample Output

4 4 10
NIR
0

2个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问