首页 > ACM题库 > HDU-杭电 > HDU 3205-Factorization-数论-[解题报告]HOJ
2014
03-06

HDU 3205-Factorization-数论-[解题报告]HOJ

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)

因为太懒太久没写题解了,NOI过后变得更懒…

顺便从wyl8899神犇那里抽一题出来练练手吧…

 

题目简述:

      给出正整数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;

}

参考:http://hi.baidu.com/liouzhou_101/item/e6105ebc0a6c73fc4ec7fd02


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