Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

请教为什么会超时??

Posted by qianyun at 2008-01-04 16:16:24 on Problem 3471
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator