P4506 [CTSC2013] Factorization

By the Fundamental Theorem of Algebra, counting multiplicity, a degree $n$ polynomial over the complex numbers has exactly $n$ zeros (points where the function value is $0$). You are given an integer-coefficient polynomial $F[x]$ whose $n$ zeros are all rational numbers (i.e., can be written as a ratio of two integers). If we deduplicate all nonzero zeros (the variable is not $0$ while the function value is $0$), we obtain $r$ distinct nonzero zeros, where the $i$-th nonzero zero can be written as: $$sgn_i \times \frac{q_i}{p_i}$$ Here $sgn_i$ denotes the sign of the $i$-th zero, and $p_i$ and $q_i$ are two coprime positive integers. You are given $F[x]$. Output its factorized form.

The input contains exactly one line: the polynomial $F[x]$. The polynomial is always given in the following form: $ a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0 $ The terms are in descending degree. Each $a_i$ is an integer. If $a_i = 0$, that term is omitted. If $a_i$ is negative, the preceding plus sign is omitted. If $|a_i| = 1$ and $i \ne 0$, the $1$ is not printed. It is guaranteed that $a_n \ne 0$. See the sample input.

Output one line: the factorized form in the following format: $ a_n (x + u_1 / v_1)^{t_1} (x + u_2 / v_2)^{t_2} \cdots (x + u_s / v_s)^{t_s} $ Here $u$ and $v$ are coprime, and $v$ is a positive integer. $u_i / v_i$ are sorted from largest to smallest. If $u_i / v_i = 0$, that factor is $x^{t_i}$. If $u_i / v_i$ is negative, the plus sign is omitted. If $v_i = 1$, then $/ v_i$ is omitted. If $t_i = 1$, the exponent is omitted. If $a_n = \pm 1$, the $1$ is omitted. See the sample output.

测试点编号|多项式最高次数|互异零点数|系数范围(绝对值) :-:|:-:|:-:|:-: $1$|$2$|$2$|$\le 10$ $2$|$4$|$4$|$\le 100$ $3$|$7$|$7$|$\le 10^6$ $4$|$10$|$10$|$\le 10^7$ $5$|$12$|$12$|$\le 10^{16}$ $6$|$35$|$5$|$\le 10^{24}$ $7$|$39$|$5$|$\le 10^{68}$ $8$|$46$|$4$|$\le 10^{104}$ $9$|$80$|$2$|$\le 10^{12}$ $10$|$50$|$1$|$\le 10^{316}$ $p_i, q_i$ satisfy: $$\prod_{i=1}^r p_i \le 10^6, \prod_{i=1}^r q_i \le 10^6.$$ Translated by ChatGPT 5