integer roots of a polynomial.cpp

数值分析中常用的几种算法的实现

#include<stdio.h>
int a[30],b[30];
int yueshu[10000];
int abs(int x){
	if(x>0)
		return x;
	else
		return -1*x;
}
int main(){
	int deg,i,j,k,cas,all,flag,zero,c;
	freopen("test.txt","r",stdin);
	scanf("%d",&cas);
	while(cas--){
		scanf("%d",&deg);
		for(i=deg;i>=0;i--)
			scanf("%d",&a[i]);
		yueshu[0]=1;
		all=1;
		c=abs(a[0]);
		for(i=2;i<=c;i++){
			if(c%i==0){
				yueshu[all++]=i;
			}
		}
		for(i=0;i<=deg;i++){
			if(a[i]!=0){
				break;
			}
		}
		zero=i;
		for(i=zero;i<=deg;i++){
			a[i-zero]=a[i];
		}
		deg-=zero;
		flag=0;
		for(i=all-1;i>=0;i--){
			k=yueshu[i];
			if(a[0]%k!=0)
				continue;
			b[0]=a[0]/k;
			for(j=1;j<deg;j++){
				if((a[j]-b[j-1])%k==0)
					b[j]=(a[j]-b[j-1])/k;
				else
					break;
			}
			if(j==deg&&b[deg-1]==a[deg]){
				deg--;
				if(flag==0)
					printf("%d",-1*k);
				else printf(" %d",-1*k);
				flag=1;
				for(j=0;j<=deg;j++)
					a[j]=b[j];
				i++;
			}
		}
		for(i=0;i<zero;i++){
			if(flag)
				printf(" 0");
			else
				printf("0");
			flag=1;
		}
		for(i=0;i<all;i++){
			k=-1*yueshu[i];
			if(a[0]%k!=0)
				continue;
			b[0]=a[0]/k;
			for(j=1;j<deg;j++){
				if((a[j]-b[j-1])%k==0)
					b[j]=(a[j]-b[j-1])/k;
				else
					break;
			}
			if(j==deg&&b[deg-1]==a[deg]){
				deg--;
				if(flag==0)
					printf("%d",-1*k);
				else printf(" %d",-1*k);
				flag=1;
				for(j=0;j<=deg;j++)
					a[j]=b[j];
				i--;
			}
		}
		
		if(flag==0)
			printf("NIR");
		printf("\n");
	}
}