Finding All Rational Roots of a Polynomial

Given a univariate polynomial equation:

\(a_0 + a_1x + a_2x^2 + \dots + a_nx^n = 0\)

with integer coefficients (where \(a_n \neq 0\)), the task is to find all rational roots of the equation.

For each rational root, output it as an irreducible fraction (e.g. p/q) if it is not an integer, or simply as an integer if the denominator is 1. The roots should be printed in increasing order and no duplicate roots should be output. If there is no rational root, output NO.

This problem can be solved using the Rational Root Theorem. According to the theorem, any rational solution \(\frac{p}{q}\) (in lowest terms) must satisfy that p divides \(a_0\) (the constant term) and q divides \(a_n\) (the leading coefficient).

inputFormat

The first line contains a single integer n (\(1 \le n \le 10\) for example) representing the degree of the polynomial.

The second line contains \(n+1\) space-separated integers: \(a_0, a_1, \dots, a_n\), where \(a_n \neq 0\). These represent the coefficients of the polynomial in increasing order of the power of x.

outputFormat

If there is at least one rational root, output all distinct roots in increasing order separated by a single space. Express each root as:

• an integer if the denominator is 1, or
• an irreducible fraction in the form p/q otherwise.

If no rational roots exist, output NO (without quotes).

sample

2
1 -3 2

1/2 1