大整数乘法.cpp

大整数乘法 poj 2980 比一般的算法快一点点哦

#include <iostream>
#include <cstring>
using namespace std;

char z[300]={0};
void Multi(char *p, char *q);
int main()
{
	char x[300],y[300];
	cin>>x>>y;
	Multi(x,y);
	cout<<z<<endl;
}
void Multi(char x[300], char y[300])
{
	
	int a[300],b[300],m[300]={0},n[300]={0},c[300]={0};
	int lenx,leny,unitx,unity,sum;
	int i,j=0,k,l,s;
	int t=0;


	lenx=strlen(x);
	leny=strlen(y);
	unitx=lenx/4;
	unity=leny/4;
	sum=unitx+unity+1;

	
	for (i = lenx-1; i >= 0; i--)
	{	
		m[j++]=x[i]-'0';
	}

	j=0;

	for (i = leny-1; i >= 0; i--)
	{
		n[j++]=y[i]-'0';
	}
	for (i = 0,j = 0; i <= unitx+1; i++,j+=4)
	{
		a[i] = m[j] + m[j+1]*10 + m[j+2]*100 + m[j+3]*1e3;
	}
	
	for (i = 0,j = 0; i <= unity+1; i++,j+=4)
	{
		b[i] = n[j] + n[j+1]*10 + n[j+2]*100 + n[j+3]*1e3;
	}

	for (i = 0; i <= unitx; i++)
	{
		for (j = 0; j <= unity; j++)
		{
			s = c[i+j] + a[i]*b[j];
			if (s>=1e4)
			{
				c[i+j+1] += s/1e4;
			}
			c[i+j] = s % 10000;
			s = 0;
		}
	}
	while (c[sum]==0)
	{
		sum--;
	}
	
	for (i = sum; i >= 0; i--)
	{
		l=1;
		for (k = 3; k >= 0; k--)
		{
			l*=10;
			if (!(c[i]/l)) break;
		}
		
		for (j=3;j>=0;j--)
		{
			z[t+j]=c[i]%10+'0';
			c[i]/=10;
		}
		t=t+4;

	}
	z[t]='\0';

	i=0;
	while (z[i]=='0') i++;
	strcpy(z,&z[i]);
}