题目实际上就是要求f(x)=0的整数根。

观察一个不少于1次的多项式f(x)
设f(x)=g(x)*x+a
那么f(x)=0蕴含着：a=0且x=0，或者x|a
这是一个十分重要的结论！我们可以枚举a的因数作为x的实验值，依次带入即可
可以用递归的方法来解决

解决f(x):
  如果f(x)少于1次，直接返回
  设f(x)=g(x)*x+a
  如果a=0
    x=0是一个根。递归解决f(x)/x并返回
  否则
    枚举a的因数x'。若f(x')=0
       x=x'是一个根。递归解决f(x)/(x-x')并返回
    如果没有x'使f(x')=0，返回

我枚举因数的方法是质因数分解，再枚举每个质因数的次数。
注意：
1.质因数分解的结果可能包含超过sqrt(2^31)的质数
2.若x是a的因数，-x也是

那么如何判断f(x)是否为0呢？
高精度显然是个糟糕的主意。
我的方法：取模。
用霍纳法则展开多项式，
f(x)=(...(an*x+a(n-1))*x+a(n-2))*x+a(n-3)......)*x+a0
每一次计算后都取模p
如何选取p是一门艺术。
我的方法：选若干个大质数，分别用他们作为p，多次测试。
我选取了7个质数：
long long mods[]={
13251349,
13251361,
13251367,
13251373,
13251377,
13251383,
13251391};
这样，如果因为此出错，那我立刻去买六合彩。

几个细节
1.强烈建议使用long long
注意这个数据：
1
-2147483648
2.枚举一次项系数的因数是个耗时的工作。然而，你会发现：
每一次枚举的结果都是上一次枚举的子集！
换句话说，把输入的a0分解并枚举质因数后，这个结果可以多次利用，
并且如果某次尝试过x=i失败后，以后可以不用尝试x=i
3.如果使用了第2条优化，那么一定注意a0=0的情况
4.排序输出！排序输出！

关键代码：
void gen(long long b,int i){
	if (i==dc)list[lc++]=b;
	else{
		for (int j=0;j<=divc[i];j++){
			gen(b,i+1);
			b*=divs[i];
		}
	}
}
void gen(long long a){
	lc=0;dc=0;
	long long t;
	t=a;
	for (int i=0;i<pc;i++)if (t%(long long)prime[i]==0){
		divs[dc]=prime[i];divc[dc]=0;
		while (t%(long long)prime[i]==0){
			divc[dc]++;
			t/=(long long)prime[i];
		}
		dc++;
	}
	if (t!=1)divs[dc++]=t;
	gen(1,0);
}
long long mods[]={
13251349,
13251361,
13251367,
13251373,
13251377,
13251383,
13251391};
#define MODC 7
int test(long long a){
	long long r,b;
	for (int i=0;i<MODC;i++){
		r=0;
		b=a%mods[i];
		for (int j=N;j>=0;j--)r=(r*b+coef[j])%mods[i];
		if (r)return 0;
	}
	return 1;
}

	for (int i=0;i<47000;i++)isp[i]=1;
	isp[0]=isp[1]=0;pc=0;
	for (int i=0;i<47000;i++)if (isp[i]){
		prime[pc++]=i;
		if (i<300)for (int j=i*i;j<47000;j+=i)
			isp[j]=0;
	}
	while (scanf("%d",&N)!=EOF){
		for (int i=N-1;i>=0;i--)scanf("%I64d",coef+i);
		coef[N]=1;R=0;li=0;lc=0;
		while (N){
			if (coef[0]==0){
				root[R++]=0;
				for (int i=0;i<N;i++)coef[i]=coef[i+1];
				N--;
			}else{
				if (!lc)gen(Abs(coef[0]));
				t=0;
				for (int i=li;i<lc;i++){
					if (coef[0]%list[i]==0 && test(list[i])){t=list[i];li=i;break;}
					if (coef[0]%list[i]==0 && test(-list[i])){t=-list[i];li=i;break;}
				}
				if (!t)break;
				root[R++]=t;r=0;
				for (int i=N;i>=0;i--){
					//r*x+c[i]  /   x-t  =  r ... rt+c[i]
					u=r*t+coef[i];coef[i]=r;r=u;
				}
				N--;
			}
		}
		for (int i=0;i<R;i++)for (int j=i+1;j<R;j++)
			if (root[i]>root[j])
				t=root[i],root[i]=root[j],root[j]=t;
	}

• 谢谢你的详细解答，已学习，留名一下！ (0) inowfordream 2010-04-14 23:22:18
• Re:太强了。。。顶！！！！！！！ (2824) 19891101 2012-09-28 22:24:44