hdu 4447 Yuanfang, What Do You Think?

思路：
这题有个结论也可以自己归纳：
对于给定的n，其约数用pi表示
T(n)=T(p1)T(p2)……T(pn)T(n')
其中T(n')是这个式子所独有的也就是
T(n')=(x^n-1)/T(p1)/T(p2)……/T(pn)
代码如下：
  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<algorithm>
  4 #include<iomanip>
  5 #include<cmath>
  6 #include<cstring>
  7 #define MAX 1102
  8 using namespace std;
  9 struct pol
 10 {
 11     int bit[MAX],len;
 12     void init(){memset(bit,0,sizeof(bit));len=1;}
 13 }p[MAX];
 14 int ans[MAX];
 15 int com(pol a,pol b)
 16 {
 17     if(a.len!=b.len)return a.len-b.len;
 18     for(int i=a.len-1;i>=0;i--)
 19         if(a.bit[i]!=b.bit[i]){
 20             if(abs(a.bit[i])!=abs(b.bit[i]))
 21                 return abs(a.bit[i])-abs(b.bit[i]);
 22             return a.bit[i]-b.bit[i];
 23         }
 24     return 0;
 25 }
 26 bool cmp(int a,int b)
 27 {
 28     return com(p[a],p[b])<0;
 29 }
 30 void shows(int n)
 31 {
 32     if(n>1) printf("x^%d",n);
 33     else if(n==1) printf("x");
 34 }
 35 void show(pol a)
 36 {
 37     int x;
 38     printf("(");
 39     for(int i=a.len-1;i>=0;i--){
 40         if(a.bit[i]==0) continue;
 41         if(i==0){
 42             if(a.bit[i]>0) printf("+%d",a.bit[i]);
 43             else printf("%d",a.bit[i]);
 44             continue;
 45         }
 46         if(i==a.len-1){
 47             if(a.bit[i]<0) printf("-");
 48             x=abs(a.bit[i]);
 49             if(x>1) printf("%d",x);
 50             shows(i);
 51             continue;
 52         }
 53         if(a.bit[i]<0) printf("-");
 54         else printf("+");
 55         x=abs(a.bit[i]);
 56         if(x>1) printf("%d",x);
 57         shows(i);
 58     }
 59     printf(")");
 60 }
 61 pol Div(pol a,pol b)
 62 {
 63     pol c;
 64     c.init();
 65     for(int i=a.len-1;i>=0;i--)
 66         if(a.bit[i]){
 67         c.bit[i-b.len+1]=a.bit[i];
 68         int cnt=0,cur=a.bit[i];
 69         for(int j=b.len-1;j>=0;j--){
 70             a.bit[i-cnt]-=cur*b.bit[j];
 71             cnt++;
 72         }
 73     }
 74     c.len=a.len;
 75     while(c.len>1&&c.bit[c.len-1]==0) c.len--;
 76     return c;
 77 }
 78 int main(){
 79     p[1].bit[0]=-1;
 80     p[1].bit[1]=1;
 81     p[1].len=2;
 82     for(int i=2;i<MAX;i++){
 83         p[i].init();
 84         p[i].bit[i]=1;p[i].bit[0]=-1;
 85         p[i].len=i+1;
 86         p[i]=Div(p[i],p[1]);
 87         for(int j=2;j*j<=i;j++){
 88             if(i%j==0){
 89                 p[i]=Div(p[i],p[j]);
 90                 if(j*j!=i) p[i]=Div(p[i],p[i/j]);
 91             }
 92         }
 93     }
 94     int n,m;
 95     while(scanf("%d",&n)&&n){
 96         if(n==1){
 97             puts("x-1");
 98             continue;
 99         }
100         m=0;
101         for(int i=1;i*i<=n;i++){
102             if(n%i==0){
103                 ans[m++]=i;
104                 if(i*i!=n) ans[m++]=n/i;
105             }
106         }
107         sort(ans,ans+m,cmp);
108         for(int i=0;i<m;i++)
109             show(p[ans[i]]);
110         printf("
");
111     }
112     return 0;
113 }
View Code