2014
03-06

# Factorization

LMY and YY are mathematics lovers. They like to find and solve interesting mathematic problems together. One day, they found that the polynomial “x^n-1” can be factorized into a large number of long polynomials, although the polynomial “x^n-1” looks simple. They were interested in how to factorize it into irreducible polynomials.

By “irreducible” we mean that it has co-prime coefficients and cannot be further factorized.

Now your task is to help LMY and YY to factorize x^n-1 into several irreducible polynomials over the integers.

The input consists of multiple test cases.
For each test case, there is one line containing only one integer N. (2<=N<=1001)

End of input is indicated by a line containing a zero.

The input consists of multiple test cases.
For each test case, there is one line containing only one integer N. (2<=N<=1001)

End of input is indicated by a line containing a zero.

2
3
4
5
6
12
256
0

(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-1)(x+1)(x^2+1)(x^2-x+1)(x^2+x+1)(x^4-x^2+1)
(x-1)(x+1)(x^2+1)(x^4+1)(x^8+1)(x^16+1)(x^32+1)(x^64+1)(x^128+1)

给出正整数N(2≤N≤1,001)，分解因式x^N-1。

我们证明

定理：若a|b，则多项式(x^a-1)可以整除(x^b-1)。

首先先证明一个引理：

引理：对任意正整数N，多项式(x-1)可以整除(x^N-1)。

引理证明：因式分解得x^N-1=(x-1)(x^(N-1)+x^(N-2)+…+x^2+x+1)。

定理证明：

令b=ka，那么令y=x^a，则x^b=y^k。

由引理得多项式(y-1)可以整除(y^k-1)，于是定理得证。

所以对于一个N，(x^M-1)(任意N的约数M)的所有因式都是x^N-1的因式。

因此我们就可以依次求出x^N-1的因式分解形式。

update:

当我们把所有n的因子m枚举了之后，就得到了其中一些的x^N-1的因式。

而剩下的因式一定只有一个，且这个因式不可分解。（怎么证？）

还有就是一定不会出现这种情况：存在A是x^N-1的因式，A^2也是x^N-1的因式。（怎么证？）

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<utility>

using namespace std;

map<int,int> tmp;

set<map<int,int> > ans[1010];

int a[1010],b[1010],c[1010];

bool cmp(vector<pair<int,int> > A,vector<pair<int,int> > B)

{

vector<pair<int,int> >::reverse_iterator pA=A.rbegin(),pB=B.rbegin();

while (1)

{

if (pA->first<pB->first) return true;

if (pA->first>pB->first) return false;

if (abs(pA->second)<abs(pB->second)) return true;

if (abs(pA->second)>abs(pB->second)) return false;

if (pA->second<pB->second) return true;

if (pA->second>pB->second) return false;

++pA;++pB;

}

}

void init()

{

tmp[1]=1;

tmp[0]=-1;

ans[1].insert(tmp);

for (int i=2;i<=1001;++i)

{

for (int j=1;j<i;++j)

if (i%j==0)

for (set<map<int,int> >::iterator p=ans[j].begin();p!=ans[j].end();++p)

ans[i].insert(*p);

for (int j=0;j<=i;++j) a[j]=0;

a[i]=1;

a[0]=-1;

for (set<map<int,int> >::iterator p=ans[i].begin();p!=ans[i].end();++p)

{

for (int j=0;j<=i;++j) b[j]=c[j]=0;

for (std::_Rb_tree_const_iterator<std::pair<const int, int> > it=p->begin();it!=p->end();++it)

b[it->first]=it->second;

int get=0;

for (int j=0;j<=i;++j) if (b[j]) get=j;

for (int j=i;j>=0;–j)

if (a[j])

{

c[j-get]=a[j];

for (int k=get;k>=0;–k)

a[j-get+k]-=c[j-get]*b[k];

}

for (int j=i;j>=0;–j) a[j]=c[j];

}

tmp.clear();

for (int j=i;j>=0;–j)

if (a[j]) tmp[j]=a[j];

ans[i].insert(tmp);

}

}

void work()

{

while (1)

{

int n;

scanf("%d",&n);

if (!n) return;

vector<vector<pair<int,int> > > v;

v.clear();

vector<pair<int,int> > w;

for (set<map<int,int> >::iterator p=ans[n].begin();p!=ans[n].end();++p)

{

w.clear();

for (std::_Rb_tree_const_iterator<std::pair<const int, int> > it=p->begin();it!=p->end();++it)

w.push_back(make_pair(it->first,it->second));

v.push_back(w);

}

sort(v.begin(),v.end(),cmp);

for (vector<vector<pair<int,int> > >::iterator p=v.begin();p!=v.end();++p)

{

w=*p;

putchar('(');

int flag=0;

for (vector<pair<int,int> >::reverse_iterator it=w.rbegin();it!=w.rend();++it)

{

if (flag) putchar((it->second>0)?'+':'-');

it->second=abs(it->second);

if (it->first==0) printf("%d",it->second);

else if (it->first==1) (it->second==1)?putchar('x'):printf("%dx",it->second);

else (it->second==1)?printf("x^%d",it->first):printf("%dx^%d",it->second,it->first);

flag=1;

}

putchar(')');

}

puts("");

}

}

int main()

{

init();

work();

return 0;

}

1. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。