P4598 [HEOI2012] Akai's Math Homework

Here lies the vast universe. Here flows the mighty Milky Way. Here is the one-and-only Solar System. Here is the blue Earth. Here, right here, is the fertile Chinese mainland. Here is the magical land of Hebei. Here is the beautiful city of Tangshan. Here is the mythical Tangshan No. 1 High School. Here is the classroom where Akai once studied.

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$: $$a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n = 0$$ 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?

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

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.

- 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