题意很简单。就是求x^k-1的因式分解。显然x-1必然是其中之一（x=1, x^k-1=0）。
假设k=mp. 则x^k = (x^p)^m, 同理x^p-1必然是其中之一，即x^p的所有因式一定是x^k的所有因式。
思路就是按照上面的方式，先找到k的约束的多项式，然后求得最后一个因式的系数。
求得所有[2,1001]的因式后。
对因式进行重新排序，并按照格式输出。输出时注意系数为1，阶数为0，阶数为1。
/* 3205 */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define mpii map<int,int>
#define sti set<int>
#define stpii set<pair<int,int> >
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 const int maxn = ;
set<stpii> ans[maxn];
int n;
int a[maxn], b[maxn]; typedef struct ele_t {
int d, c;
ele_t(int d_=, int c_=):
d(d_), c(c_) {}
friend bool operator< (const ele_t& a, const ele_t& b) {
// if (a.d == b.d)
// return a.c < b.c;
// else
// return a.d < b.d;
return a.d > b.d;
}
} ele_t; typedef struct node_t {
vector<ele_t> ele;
// int sz;
friend bool operator< (const node_t& a, const node_t& b) {
bool ret;
int c1, c2;
int sza = SZ(a.ele);
int szb = SZ(b.ele);
int mn = min(sza, szb);
ret = sza < szb; rep(i, , mn) {
if (a.ele[i].d == b.ele[i].d) {
c1 = abs(a.ele[i].c);
c2 = abs(b.ele[i].c);
if (c1 == c2) {
if (a.ele[i].c == b.ele[i].c)
continue;
ret = a.ele[i].c < b.ele[i].c;
} else {
ret = c1 < c2;
}
break;
} else {
ret = a.ele[i].d < b.ele[i].d;
break;
}
} return ret;
}
} node_t; vector<node_t> nd[maxn];
void init();
void resort(); int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int x;
int deg, coe;
// set<stpii>::iterator iter, eiter;
// stpii::iterator siter, esiter;
vector<node_t>::iterator iter, eiter;
vector<ele_t>::iterator siter, esiter;
bool flag; init();
while (scanf("%d",&x)!=EOF && x) {
iter = nd[x].begin();
eiter = nd[x].end();
while (iter != eiter) {
siter = iter->ele.begin();
esiter = iter->ele.end();
flag = true;
putchar('(');
while (siter != esiter) {
deg = siter->d;
coe = siter->c;
if (flag) {
if (deg == ) {
printf("x");
} else {
printf("x^%d", deg);
}
} else {
if (deg == ) {
if (coe > ) {
putchar('+');
} else {
putchar('-');
coe = -coe;
}
printf("%d", coe);
} else if (deg == ) {
if (coe > ) {
putchar('+');
} else {
putchar('-');
coe = -coe;
}
if (coe == ) {
printf("x");
} else {
printf("%dx", coe);
}
} else {
if (coe > ) {
putchar('+');
} else {
putchar('-');
coe = -coe;
}
if (coe == ) {
printf("x^%d", deg);
} else {
printf("%dx^%d", coe, deg);
}
}
}
flag = false;
++siter;
}
putchar(')');
++iter;
}
putchar('\n');
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
} void init() {
stpii st;
stpii::iterator it;
set<stpii>::iterator iter, eiter;
int i, j, k;
int v, mx;
int deg, coe; // x - 1
st.insert(mp(, ));
st.insert(mp(, -));
for (v=; v<maxn; ++v)
ans[v].insert(st); for (v=; v<maxn; ++v) { for (i=; i*i<=v; ++i) {
if (v%i == ) {
j = v / i;
for (iter=ans[i].begin(); iter!=ans[i].end(); ++iter)
ans[v].insert(*iter);
if (j != i) {
for (iter=ans[j].begin(); iter!=ans[j].end(); ++iter)
ans[v].insert(*iter);
}
}
} st.clear();
iter = ans[v].begin();
eiter = ans[v].end(); // init a with const 1
memset(a, , sizeof(a));
a[] = ; // multiply other elements
while (iter != eiter) {
memset(b, , sizeof(b));
for (it=iter->begin(); it!=iter->end(); ++it) {
deg = it->fir;
coe = it->sec;
for (j=; j<=v; ++j) {
b[j+deg] += coe * a[j];
}
}
memcpy(a, b, sizeof(a));
++iter;
} memset(b, , sizeof(b));
// find the max deg
for (mx=v; mx>=; --mx) {
if (a[mx]) {
break;
}
}
assert(mx >= ); for (j=v; j>;--j) {
if (j == v) {
coe = ;
deg = j - mx;
} else if (j == ) {
coe = --b[j];
deg = j - mx;
} else {
coe = -b[j];
deg = j - mx;
} if (coe == )
continue; for (k=mx; k>=; --k)
b[k+deg] += a[k] * coe; st.insert(mp(deg, coe));
}
ans[v].insert(st);
} resort();
} void resort() {
stpii::iterator it, eit;
set<stpii>::iterator iter, eiter;
int v, m;
int i, j, k;
int deg, coe;
ele_t e;
node_t node; for (v=; v<maxn; ++v) {
iter = ans[v].begin();
eiter = ans[v].end();
while (iter != eiter) {
node.ele.clear();
it = iter->begin();
eit = iter->end();
m = ;
while (it != eit) {
e.d = it->fir;
e.c = it->sec;
node.ele.pb(e);
++m;
++it;
}
sort(all(node.ele));
nd[v].pb(node);
++iter;
}
sort(all(nd[v]));
}
}