大数最大公约数_200612119046.txt

里面包括了一些acm比赛是常用的函数

#include<stdio.h>
#include<string.h>
#define N 101
int compare(char * c1,int s1,int e1,char *c2,int s2,int e2)/*大整数比较大小*/
{
	while(c1[s1]=='0'&&s1<e1)s1++;
	while(c2[s2]=='0'&&s2<e2)s2++;
	if(e1-s1>e2-s2)return 1;
	if(e1-s1<e2-s2)return -1;
	int i1;int f11=0;
	for(i1=0;i1<=e1-s1;i1++)
	{
		if(c1[s1+i1]>c2[s2+i1]){f11=1;break;}
		if(c2[s2+i1]>c1[s1+i1])break;
	}
	if(i1>e1-s1)return 0;
	if(f11)return 1;
	return -1;
}
void sub(char *c1,int l1,char *c2,int n,int l)/*两个大整数相减*/
{
	int fig=0;
	if(l1>l)
	{
		fig=1;
		int i5;
		for(i5=l;i5>0;i5--)
			c2[i5]=c2[i5-1];
		c2[0]='0';l++;
	}
	int jw=0;
	int i4;
	char tc[N];
	for(i4=l-1;i4>=0;i4--)
	{
		tc[i4]=((c2[i4]-48)*n+jw)%10+48;
		jw=((c2[i4]-48)*n+jw)/10;
	}
	jw=0;
	for(i4=l-1;i4>=0;i4--)
	{
		int ttt=jw;
		if(c1[i4]-tc[i4]-jw>=0)
		{
			tc[i4]=c1[i4]-tc[i4]-jw+48;
			jw=0;
		}
		else
		{

			jw=(tc[i4]-c1[i4]+jw);
			if(jw%10==0)jw/=10;
			else jw=jw/10+1;
			tc[i4]=jw*10+c1[i4]-tc[i4]-ttt+48;
		}
	}
	if(fig)
	{
		for(i4=0;i4<l-1;i4++)c2[i4]=c2[i4+1];

		l--;
		c2[l]='\0';
	}
	tc[l1]='\0';
	for(i4=0;i4<=l1;i4++)
		c1[i4]=tc[i4];
}
void high_precise_division(char *c1,char *c2)
{
	int len1,len2;
	len1=strlen(c1);
	len2=strlen(c2);
	int i,j,k,iiip;
	while(c1[0]=='0'&&len1>1)
	{
		for(k=0;k<len1-1;k++)
			c1[k]=c1[k+1];
		len1--;
	}/*去掉前面的0*/
	while(c2[0]=='0'&&len2>1)
	{
		for(k=0;k<len2-1;k++)
			c2[k]=c2[k+1];
		len2--;
	}/*去掉前面的0*/
	c1[len1]='\0';
	c2[len2]='\0';
	if(c2[0]=='0'&&len2==1)return ;/*当除数为0时停止计算，返回*/
	if(len1<len2||len1==len2&&compare(c1,0,len1-1,c2,0,len2-1)<0)
	{
		strcpy(c2,c1);
		c1[0]='0';c1[1]='\0';
		return ;
	}
	else
	{
		iiip=0;
		char product[N],*pr;/*部分积*/
		pr=product;
		for(iiip=0;iiip<len2-1;iiip++)
			pr[iiip]=c1[iiip];
		for(i=0;i<=len1-len2;i++)
		{
			pr[iiip++]=c1[len2-1+i];
			if(iiip>=len2&&compare(pr,0,iiip-1,c2,0,len2-1)>=0)
			{
				char tc[N];
				for(j=1;j<=9;j++)//100000 112121
				{
					for(k=0;k<iiip;k++)tc[k]=pr[k];	
					sub(tc,iiip,c2,j,len2);/*pr-c2*j结果放在pr中*/
					for(k=0;tc[k]!='\0';k++);
					if(compare(tc,0,k-1,c2,0,len2-1)<0)
						break;
				}
				strcpy(pr,tc);
				iiip=strlen(pr);
				c1[i]=j+48;
				while(pr[0]=='0'&&iiip>1)
				{
					for(j=0;j<iiip-1;j++)
						pr[j]=pr[j+1];
					iiip--;
				}
				if(iiip==1&&pr[0]=='0')iiip--;
			}
			else c1[i]='0';
		}
		while(c1[0]=='0')
		{
			for(j=0;j<i-1;j++)
				c1[j]=c1[j+1];
			i--;
		}
		c1[i]='\0';
		if(iiip==0){pr[0]='0';pr[1]='\0';iiip=1;}
		else
		{
			while(pr[0]=='0'&&iiip>1)
			{
				for(j=0;j<iiip-1;j++)pr[j]=pr[j+1];
				iiip--;
			}
		}
		for(j=0;j<iiip;j++)
			c2[j]=pr[j];
		c2[iiip]='\0';
	
		return ;
	}
}
char * co(char *m,char *n)/*求大数最大公约数,要用到上面三个子函数*/
{
	if(strlen(n)==1&&n[0]=='0')return m;
	else
	{
		int i;
		char tc[N];
		for(i=0;i<strlen(n)&&n[i]!='\0';i++)
			tc[i]=n[i];
		tc[i]='\0';
		high_precise_division(m,n);
		for(;i>=0;i--)m[i]=tc[i];
		return co(m,n);
	}
}
int main()
{
	int ii=0,j;
	char c1[N],c2[N];
	while(scanf("%s %s",c1,c2)!=EOF)
	{
		char *pc1,*pc2;
		pc1=c1;pc2=c2;
		c1[strlen(c1)]='\0';
		c2[strlen(c2)]='\0';
		printf("%s\n",co(pc1,pc2));/*示例*/
		ii++;
	}
	return 0;
}