Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
请教为什么会超时??#include<iostream> #include<cstdio> #include<cmath> using namespace std; _int64 pow(_int64 x,_int64 n) { _int64 result=1; for(_int64 i=0;i<n;i++) result*=x; return result; } int compare(const void *s1,const void *s2) { if(*(_int64*)s1<*(_int64*)s2) return -1; else if(*(_int64*)s1>*(_int64*)s2) return 1; else return 0; } class Polynomial { public: Polynomial(_int64 n) { item=n; for(int i=n-1;i>=0;i--) scanf("%I64d",&coefficient[i]); coefficient[n]=1; rootnum=0; } void output() { findroot(); printf("%I64d\n",rootnum); qsort(root,rootnum,sizeof(_int64),compare); for(_int64 i=0;i<rootnum;i++) { printf("%I64d\n",root[i]); } } private: _int64 calculate(_int64 testroot) { _int64 result=pow(testroot,item); for(_int64 i=0;i<item;i++) result+=coefficient[i]*pow(testroot,i); return result; } void findroot() { while(coefficient[0]==0) { root[rootnum++]=0; item--; for(_int64 i=0;i<item;i++) coefficient[i]=coefficient[i+1]; } for(_int64 j=1;j<sqrt(fabs(static_cast<double>(coefficient[0])))+0.5;j++) { if(coefficient[0]%j==0) { _int64 i; while(calculate(j)==0) { i=j; root[rootnum++]=i; item--; coefficient[0]=-coefficient[0]/i; for(_int64 k=1;k<item;k++) { if((coefficient[k-1]-coefficient[k])%i) return; coefficient[k]=(coefficient[k-1]-coefficient[k])/i; } coefficient[item]=1; } i=j; while(calculate(-j)==0) { i=-j; root[rootnum++]=i; item--; coefficient[0]=-coefficient[0]/i; for(_int64 k=1;k<item;k++) { if((coefficient[k-1]-coefficient[k])%i) return; coefficient[k]=(coefficient[k-1]-coefficient[k])/i; } coefficient[item]=1; } } if(item==0) break; } for(_int64 k=1;k<sqrt(fabs(static_cast<double>(coefficient[0])))+0.5;k++) { if(coefficient[0]%k==0) { _int64 i,j=coefficient[0]/k; while(calculate(j)==0) { i=j; root[rootnum++]=i; item--; coefficient[0]=-coefficient[0]/i; for(_int64 k=1;k<item;k++) { if((coefficient[k-1]-coefficient[k])%i) return; coefficient[k]=(coefficient[k-1]-coefficient[k])/i; } coefficient[item]=1; } i=j; while(calculate(-j)==0) { i=-j; root[rootnum++]=i; item--; coefficient[0]=-coefficient[0]/i; for(_int64 k=1;k<item;k++) { if((coefficient[k-1]-coefficient[k])%i) return; coefficient[k]=(coefficient[k-1]-coefficient[k])/i; } coefficient[item]=1; } } if(item==0) break; } } _int64 coefficient[101]; _int64 root[101]; _int64 rootnum; _int64 item; }; int main() { _int64 n; while(scanf("%I64d",&n)!=EOF) { Polynomial poly(n); poly.output(); } } 代码如上,基本思路就是在1~sqrt(abs(coefficient[0]))的数中求coefficient[0]的所有因子,再逐个试验,若t是根,则将多项式除x-t. Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator