超长整数的四则运算.txt

此算法实现超长整数（计算机所不能表示的整数

#include<stdio.h>
#include <string.h> 
#define MAXCHAR 300
#define MAX 300
void Add (char *ch1 , char *ch2 , char *ch3) //ch1+ch2=ch3
{ 
    int len1=strlen(ch1),len2=strlen(ch2),len3,i,tmp,num1[MAX],num2[MAX],num3[MAX]; 
    memset (num1 , 0 , sizeof(num1)); 
    memset (num2 , 0 , sizeof(num2)); 
    memset (num3 , 0 , sizeof(num3)); 

    for (i=len1-1;i>=0;i--) num1[len1-1-i] = ch1[i] - 48;
    for (i=len2-1;i>=0;i--) num2[len2-1-i] = ch2[i] - 48; 

    i=0,tmp=0,len3=len1>len2?len1:len2; 
    while (i < len3) 
	{ 
       num3[i] = num1[i] + num2[i] + tmp; 
       tmp = 0; 
    if (num3[i] >= 10) { tmp = num3[i]/10; num3[i] %= 10; } 
    i ++; 
	} 
    if(tmp!=0){num3[i] = tmp; i ++; } 
       len3 = i; 
    for (i=len3-1;i>=0;i--) ch3[len3-1-i] = num3[i] + 48; 
    ch3[len3] = '\0'; 
    return ; 
} 

void Minus (char *ch1 , char *ch2 , char *ch3) //ch1-ch2=ch3
{ 
    int i,tmp,len1=strlen(ch1),len2=strlen(ch2),len3,num1[MAX],num2[MAX],num3[MAX]; 
    memset (num1 , 0 , sizeof(num1)); 
    memset (num2 , 0 , sizeof(num2)); 
    memset (num3 , 0 , sizeof(num3)); 
    for (i=0;i<len1;i++) num1[len1-1-i] = ch1[i] - 48;
	for (i=0;i<len2;i++) num2[len2-1-i] = ch2[i] - 48; 

    i = 0 , tmp = 0 , len3 = len1 > len2 ? len1 : len2; 
    while (i < len3) 
	{ 
        num3[i] = num1[i] - num2[i] - tmp; 
    if (num3[i] < 0) { num3[i] += 10 , tmp = 1; } 
    else tmp = 0; 
    i ++; 
	} 

    while (len3 > 1 && num3[len3-1] == 0) len3 --; 
    for (i=0;i<len3;i++) ch3[i] = num3[len3-1-i] + 48; 
        ch3[len3] = '\0'; 
    return ; 
} 


int cmp (char *ch1 , char *ch2) //判断 大小 
{ 
   int i , len1 = strlen (ch1) , len2 = strlen (ch2); 
   if (len1 > len2) return 1; 
   if (len2 > len1) return -1; 
   for (i=0;i<len1;i++) 
   { 
      if (ch1[i] > ch2[i]) return 1; 
      if (ch1[i] < ch2[i]) return -1; 
   } 
   return 0; 
} 

void Div (char *ch1 , char *ch2 , char *ch3) //ch1/ch2=ch3
{ 
     int i , len1 , len2 , tmp; 
     char ch4[MAXCHAR] , ch5[MAXCHAR]; 
     ch3[0] = '0' , ch3[1] = '\0'; 

     while (cmp (ch1 , ch2) >= 0) 
	 { 
        len1 = strlen (ch1) , len2 = strlen (ch2); 
        tmp = len1-len2-1 > 0 ? len1-len2-1 : 0; 
        ch4[0] = '1'; 
        memcpy (ch5 , ch2 , (len2+1)*sizeof(char)); 
        for (i=0;i<tmp;i++) { ch4[1+i] = '0' , ch5[len2+i] = '0'; } 
        ch4[1+i] = '\0'; ch5[len2+i] = '\0'; 
        Add (ch3 , ch4 , ch3); // ch3 += ch4; 
        Minus (ch1 , ch5 , ch1); // ch1 -= ch5; 
	 }


     return ; 
} 

void Mod (char *ch1 , char *ch2) //取于ch1=ch1%ch2
{ 
   int i , len1 , len2 , tmp; 
   char ch3[MAXCHAR]; 
   while (cmp (ch1 , ch2) >= 0) 
   { 
   len1 = strlen (ch1) , len2 = strlen (ch2); 
   tmp = len1-len2-1 > 0 ? len1-len2-1 : 0; 
   memcpy (ch3 , ch2 , (len2+1)*sizeof(char)); 
   for (i=0;i<tmp;i++)
	   ch3[len2+i]='0';
   ch3[len2+i]='\0'; 
   Minus (ch1 , ch3 , ch1); //result ch1
   } 
   return ; 
}


char*mcd(char*a,char*b)
{
	Mod(a,b);
	if(a[0]=='0')
		return b;
	else
		return mcd(b,a);
}
void Mul(char*a,char*b,char*c)//乘法 a*b=c
{
	int k1,k2,i,k=0,j,s=0,kk=0,t;
	k1=strlen(a);	k2=strlen(b);
	for(i=0;i<MAX;i++)	 c[i]='0';
	c[MAX-1]='\0';

	for(i=k1-1;i>=0;i--,k++)
	{
		for(j=k2-1,kk=0;j>=0;j--,kk++)
		{
			t=((a[i]-'0')*(b[j]-'0')+s+(c[MAX-2-k-kk]-'0'))%10+'0';
			s=((a[i]-'0')*(b[j]-'0')+s+(c[MAX-2-k-kk]-'0'))/10;
			c[MAX-2-k-kk]=t;
			if(j==0){c[MAX-3-k-kk]='0'+s;s=0;}
		}
	}
	if(c[MAX-k1-k2-1]=='0')
		k=k1+k2-1;
	else
		k=k1+k2;
	for(i=0;i<k;i++)
		c[i]=c[i+MAX-k-1];
	c[k]='\0';
}
main()
{
	char a[MAX],b[MAX],m[MAX],d[MAX];
	while(scanf("%s%s",a,b)!=EOF)
	{
		Mul(a,b,m);
		strcpy(d,mcd(a,b));
		Div(m,d,a);		
		printf("%s",a);
	}
	return 0;
}