2015
07-16

# Yuanfang, What Do You Think?

Factoring a polynomial is always a hard and important issue in mathematics teaching in middle schools. Teacher Liu loves teaching this issue very much, but his students are not good at it.
Yuanfang is the best student in Teacher Liu’s class. Every time when Teacher Liu comes up with a hard problem and it seems no student can solve it, Liu always says: "Yuanfang , what do you think?"。
This week, Teacher Liu began to teach how to factor a polynomial. On Monday, Teacher Liu said : "Let’s factor x2-1 … Yuanfang, what do you think?"
On Tuesday, Teacher Liu said : "Let’s factor x3-1 … Yuanfang, what do you think?"
On Wednesday, Teacher Liu said : "Let’s factor x4-1 … Yuanfang, what do you think?"
…..
On Friday, Yuanfang got crazy. She wanted to solve this problem permanently. So she came to you, the only programmer she knows, for help.
You should write a program to factor the polynomial xn-1. In other words, represent the polynomial xn-1 by a product of irreducible polynomials in which coefficients are all integers.

There are several test cases. Every case is an integer n in a line (n≤1100) meaning that you should factor the polynomial xn-1.
Input ends with n=0.

There are several test cases. Every case is an integer n in a line (n≤1100) meaning that you should factor the polynomial xn-1.
Input ends with n=0.

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)

x^3 – 1 = (x-1)(x^2+x+1)

x^4 – 1 = (x-1)(x+1)(x^2+1)

Result  :  Accepted     Memory  :  6524 KB     Time  :  312 ms

/*
* Author: Gatevin
* Created Time:  2015/3/18 13:24:26
* File Name: Kotori_Itsuka.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;

#define maxn 1110
vector <int> v[maxn];

struct polynomial
{
int coe[maxn];
int len;
polynomial()
{
memset(coe, 0, sizeof(coe));
len = 1;
}
void output()
{
printf("(");
for(int i = len - 1; i >= 0; i--)
{
if(coe[i] == 0) continue;
if(i == 0)
{
if(coe[i] > 0) printf("+");
printf("%d", coe[i]);
continue;
}
if(coe[i] > 0 && i != len - 1) printf("+");
if(coe[i] == -1) printf("-");
if(abs(coe[i]) != 1) printf("%d", coe[i]);
if(i > 1)
printf("x^%d", i);
else printf("x");
}
printf(")");
return;
}
polynomial operator / (const polynomial pol);
};

polynomial polynomial :: operator / (const polynomial pol)
{
polynomial ret;
ret.len = len - pol.len + 1;
for(int i = len - 1; i >= pol.len - 1; i--)
{
int tim = coe[i] / pol.coe[pol.len - 1];
if(tim != 0)
{
for(int j = 0; j < pol.len; j++)
coe[i - j] -= tim*pol.coe[pol.len - 1 - j];
ret.coe[i - pol.len + 1] = tim;
}
}
return ret;
}

polynomial p[maxn];

bool cmp(int i, int j)//return p[i] < p[j]
{
if(p[i].len != p[j].len) return p[i].len < p[j].len;
for(int k = p[i].len - 1; k >= 0; k--)
if(p[i].coe[k] != p[j].coe[k])
{
if(abs(p[i].coe[k]) == abs(p[j].coe[k]))
return p[i].coe[k] < 0;
else return abs(p[i].coe[k]) < abs(p[j].coe[k]);
}
return false;
}

int main()
{
p[1].coe[0] = -1;
p[1].coe[1] = 1;
p[1].len = 2;//p[i] = (x - 1)
for(int i = 2; i <= 1100; i++)//计算p[2~1100]的特殊多项式
{
p[i].coe[0] = -1;
p[i].coe[i] = 1;
p[i].len = i + 1;
p[i] = p[i]/p[1];
v[i].push_back(1);
for(int j = 2; j*j <= i; j++)
{
if(i % j == 0)
{
p[i] = p[i]/p[j];
v[i].push_back(j);
if(j*j != i) p[i] = p[i]/p[i / j], v[i].push_back(i / j);
}
}
v[i].push_back(i);
}
int n;
while(scanf("%d", &n), n)
{
if(n == 1)
{
printf("x-1\n");
continue;
}
sort(v[n].begin(), v[n].end(), cmp);
for(int i = 0, sz = v[n].size(); i < sz; i++)
p[v[n][i]].output();
printf("\n");
}
return 0;
}