2757: 分解因式
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：
题目描述
如题，分解因式对gaosh来说实在太简单了，他希望写出一个程序来永久解决它们。 身为他的好朋友，你现在得帮助他，当然，他认为你水平有限，只给了你较简单的任务——分解x^n-1（1<=n<=1100）。
输入
输入数据有多组，每组数据一行一个整数给出n，输入数据以0为结束。 10%的数据，保证n全为2的整数次幂。另外有20%的数据，保证n全为质数。
输出
对于每组数据，输出它被分解因式后的形式。 注意输出数据没有special judge，需将各个因式排序输出，规则如下：
1、 从最高次项开始比较，依据系数来判断先后，优先级为正数<负数<零，优先级高的因式要输在前面。
2、 输出的结果不能再被分解因式。
3、 所有同类项都应被合并。
4、 系数为0的项不用输出。
5、 所有系数都为整数，每个因式最高次项为正数。
样例输入 复制
1
2
3
4
5
6
0
样例输出 复制
x-1
(x-1)(x+1)
(x-1)(x^2+x+1)
(x-1)(x+1)(x^2+1)
(x-1)(x^4+x^3+x^2+x+1)
(x-1)(x+1)(x^2-x+1)(x^2+x+1)
提示
Solution（会做的可以不看） 你高高兴兴的领了任务回去做了，突然意识到这个题并没有那么简单…… “连我都会做的！”gaosh长叹，他只好手把手教你如何解决这道题。 用一种类似于筛法的思想，一开始把x-1当做一个“质因式”，放进一个“质数表”，对于每个询问，将待分解的因式用质数表中的因式去除，当它不能被任何一个因式整除时就已经分解完毕了，并在此过程中将新产生的因式加入这个“质数表”。程序可以直接从1开始做到1100，循环以上步骤即可。 至于多项式除法，也可以以“数”的眼光来看待，就像任何一个k位十进制数都可以被分解成a[k]*10^k+a[k-1]*10^(k-1)+a[k-2]*10^(k-2)+……+a[1]一样，不同项的次数看做“个”、“十”、“百”这类的位数，系数则为各个数位上的数字。