poly.cpp

求两个多项式的最大公约式

#include<stdio.h>
#include<math.h> 
#include<time.h> 
#define size 30 
struct poly//定义多项式 
{
	__int64 x[size];//多项式的系数从第0项开始 
	int len; //次数 
};
__int64 gcd(__int64 a,__int64 b)//求两个整数的最大公约数 
{
	__int64 c;
	a=a>0?a:-a;
	b=b>0?b:-b;
	if(a<b)
	{
		c=a;
		a=b;
		b=c; 
	} 
	if(b==0)
	{
		return a; 
	} 
	while(1)
	{
		c=a%b;
		if(c==0)
		{
			break; 
		} 
		a=b;
		b=c;		 
	} 
	return b; 
} 
struct poly org(struct poly pa)//将多项式标准化 
{
	int i;
	__int64 m; 
	if(pa.len<0)
	{
		return pa;
	}
	if((pa.x)[pa.len]<0)
	{
		for(i=0;i<=pa.len;i++)
		{
			(pa.x)[i]=-(pa.x)[i]; 
		} 
	} 
	m=(pa.x)[0]; 
	for(i=1;i<=pa.len;i++)
	{
		m=gcd(m,(pa.x)[i]); 
	} 
	for(i=0;i<=pa.len;i++)
	{
		(pa.x)[i]/=m; 
	} 
	return pa; 
} 
void print(struct poly pa)//输出多项式 
{
	int i;
	if(pa.len>=0)
	{
		for(i=0;i<=pa.len-1;i++)
		{
			printf("%I64d ",(pa.x)[i]); 
		} 
		printf("%I64d\n",(pa.x)[pa.len]); 
	} 
	else
	{
		printf("0\n"); 
	} 
} 
struct poly mod(struct poly pa,struct poly pb)//多项式的取模运算 
{
	__int64 t,prod;
	int i=0,d; 
	double k; 
	if(pb.len<0)
	{
		printf("%d",1/i); 
	} 
	while(pa.len>=pb.len) 
	{
		t=gcd((pa.x)[pa.len],(pb.x)[pb.len]);
		t=(pb.x)[pb.len]/t;
		if(t!=1)
		{
			for(i=0;i<=pa.len;i++)
			{
				(pa.x)[i]*=t; 
			} 
		} 
		d=pa.len-pb.len;
		prod=(pa.x)[pa.len]/(pb.x)[pb.len]; 
		for(i=0;i<=pb.len;i++) 
		{
			(pa.x)[i+d]-=((pb.x)[i]*prod); 
		} 
		for(i=pa.len;i>=0;i--)
		{
			if((pa.x)[i]!=0)
			{
				break; 
			} 
		} 
		pa.len=i;
	} 
	return pa; 
}  
struct poly gcdpoly(struct poly pa,struct poly pb)//多项式的欧几里德算法 
{
	struct poly pc; 
	if(pa.len<pb.len)
	{
		pc=pa;
		pa=pb;
		pb=pc; 
	}
	if(pb.len<0)
	{
		return pa; 
	} 
	while(1)
	{
		pc=mod(pa,pb);
		if(pc.len<0)
		{
			break; 
		} 
		pa=pb;
		pb=pc;
	} 
	return pb; 
} 
main()
{
	int i,testcase,t=1,tim;
	struct poly pa,pb,pc; 
	tim=clock(); 
	scanf("%d",&testcase); 
	while(testcase--)
	{
		scanf("%d",&(pa.len));
		for(i=0;i<=pa.len;i++)
		{
			scanf("%I64d",&((pa.x)[i])); //输入第一个多项式的系数 
		} 
		scanf("%d",&(pb.len));
		for(i=0;i<=pb.len;i++)          //输入第二个多项式的系数 
		{
			scanf("%I64d",&((pb.x)[i])); 
		}  
		printf("Case %d:\n",t++);
		pc=gcdpoly(pa,pb);
		pc=org(pc); 
		print(pc); 
	} 
	 return 0; 
}