[CTSC2013] 因式分解
题目描述
通过代数基本定理,我们知道若计算重根,一个 n 次的多项式在复数域内恰好有 n 个零点(函数值为 0 的点)。现给定一个整系数多项式 F[x],它的 n 个零点恰好都是有理数(即可以写成两个整数相除的形式);同时,若我们把它所有的非零零点(函数自变量不为 0,函数值为 0)去重,则可以得到 r 个互不相同的非零零点,其中第 i 个非零零点可以被表示成下式:
$$sgn_i \times \frac{q_i}{p_i}$$
式中$sgn_i$表示第 i 个零点的符号,$p_i$和$q_i$为互质的两个正整数。
现在告诉你 F[x],要求你输出将他因式分解后的形式。
输入输出格式
输入格式
输入只有一行,包含多项式 F[x]。
多项式一定是如下的形式:
$a_n x$^$n + a_{n-1}x$^${n - 1} + ⋯ a_1x + a_0$
次数一定为从高到低,其中$a_i$为整数,并且若$a_i$为 0,则省略该项,若$a_i$为负数,则省略之前的加号,若$a_i$的绝对值为 1 且 i 不为 0,则不输出 1,并且保证$a_n$不为 0.
详见样例输入。
输出格式
输出一行,表示因式分解后的形式,格式如下:
$a_n (x + u_1/v_1)$^$t_1(x + u_2/v_2)$^$t_2 … (x + u_s/v_s)$^$t_s$
其中 u,v 互质,且 v 为正整数。
其中$u_i/v_i$从大到小排列,若$u_i/v_i = 0$ 则该项为 $x$^$t_i$,若$u_i/v_i$为负数,则省略加号,若$v_i$为 $1$,则省略$/v_i$。
若$t_i$为 $1$ 则省略^$t_i$。
若$a_n$为$±1$ 则将 $1$ 省略。
详见样例输出。
输入输出样例
输入样例 #1
8x^7-258x^5+2112x^3-512x
输出样例 #1
8(x-4)^2(x-1/2)x(x+1/2)(x+4)^2
输入样例 #2
-x^2+2x-1
输出样例 #2
-(x-1)^2
说明
测试点编号|多项式最高次数|互异零点数|系数范围(绝对值)
:-:|:-:|:-:|:-:
$1$|$2$|$2$|$≤ 10$
$2$|$4$|$4$|$≤ 100$
$3$|$7$|$7$|$≤ 10 ^ 6$
$4$|$10$|$10$|$≤ 10 ^ 7$
$5$|$12$|$12$|$≤ 10 ^ {16}$
$6$|$35$|$5$|$≤ 10 ^ {24}$
$7$|$39$|$5$|$≤ 10 ^ {68}$
$8$|$46$|$4$|$≤ 10 ^ {104}$
$9$|$80$|$2$|$≤ 10 ^ {12}$
$10$|$50$|$1$|$≤ 10 ^ {316}$
$p_i,q_i$满足:
$$\prod_{i=1}^rp_i≤10^6,\prod_{i=1}^rq_i≤10^6$$