| ||||||||||
| 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