http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1480. 因式分解
时间限制:6.0s   内存限制:512.0MB  
总提交次数:   AC次数:   平均分:
将本题分享到:
   
 
问题描述
  通过代数基本定理,我们知道若计算重根,一个n次的多项式在复数域内恰好有n个零点(函数值为0的点)。现给定一个整系数多项式F[x],它的n个零点恰好都是有理数(即可以写成两个整数相除的形式);同时,若我们把它所有的非零零点(函数自变量不为0,函数值为0)去重,则可以得到r互不相同的非零零点,其中第i个非零零点可以被表示成下式:sgn_i*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_1 x+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^ti,若 u_i/v_i 为负数,则省略加号,若 v_i 为1,则省略/v_i。
  若 t_i 为1则省略^ t_i。
  若 a_n 为 ±1 则将 1 省略。
  详见样例输出。
样例输入
8x^7-258x^5+2112x^3-512x
样例输出
8(x-4)^2(x-1/2)x(x+1/2)(x+4)^2
样例输入
-x^2+2x-1
样例输出
-(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 满足:
  ∏ p_i ≤10^6,∏ q_i≤10^6