Description

On the blackboard remains a piece of math homework Akai once did. It is actually not a very difficult problem:

"Given a univariate polynomial equation of degree $n$:

Find all rational solutions of this equation."

Akai still vividly remembers the nights he stayed up solving it. He even remembers how much scrap paper he wasted. But he just can’t recall the final answers. Can you help him?

Input Format

The first line contains an integer $n$. The second line contains $n + 1$ integers, representing $a_0$ to $a_n$.

Output Format

Output an integer $t$ on the first line, the number of rational solutions. Then output $t$ lines, each containing one solution. Each solution must be printed as a fraction in lowest terms, with a positive denominator. If a solution is an integer, output the integer directly. Equivalent solutions should be output only once. Output all solutions in increasing order.

3
-24 14 29 6 

3
-4
-3/2
2/3 

Hint

• For 30% of the testdata, $n \leq 10$.
• For 100% of the testdata, $n \leq 100$, $|a_i| \leq 1.3 \times 10^8$, $a_n \ne 0$.

HEOI 2012 Day 1 Task 1.

Translated by ChatGPT 5