思路：
这题有个结论也可以自己归纳：
对于给定的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 #include2 #include 3 #include 4 #include 5 #include 6 #include 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