A*B Problem

题目背景

高精度乘法模板题。

题目描述

给出两个非负整数，求它们的乘积。

输入格式

输入共两行，每行一个非负整数。

输出格式

输出一个非负整数表示乘积。

样例 #1

样例输入 #1

1 
2

样例输出 #1

2

提示

每个非负整数不超过 $10^{2000}$。

#include <bits/stdc++.h>
using namespace std; 
string PLUS (string,string);
int main()
{
	string x,y,sum="",mstr;
    int a[500001],b[500001],c[1000001],t[500001],m[500001],i,j,l,k,lena,lenb,len,lent,lenm,p=0;
    cin>>x;
    cin>>y;
    for(i=0;i<x.size();i++) a[i+1]=x[i]-'0';
	for(j=0;j<y.size();j++) b[j+1]=y[j]-'0';
	lena=i;lenb=j;
	len=max(lena,lenb);
	if(lena<lenb)
	{
		for(i=1;i<=lena;i++)
		{ 
			t[i]=a[i];
	    }
	    for(i=1;i<=lenb;i++)
	    {
	    	a[i]=b[i];
		}
		for(i=1;i<=lena;i++)
		{
			b[i]=t[i];
		}
		lent=lena;
		lena=lenb;
		lenb=lent;
	}
	if(lena<len)
	{
		l=len;
		a[len]=a[lena];
		a[lena]=0;
		for(k=lena-1;k>=1;k--)
		{
			a[l-1]=a[k];
			a[k]=0;
			l--;
		}
	}
	if(lenb<len)
	{
		l=len;
		b[len]=b[lenb];
		b[lenb]=0;
		for(k=lenb-1;k>=1;k--)
		{
			b[l-1]=b[k];
			b[k]=0;
			l--;
		}
	}
	bool z; 
	for(i=len;i>=1;i--)
	{
		lenm=len;
		mstr="";
		z=false;
		if(b[i]==0) mstr="0";
		else
		{
			for(j=len;j>=1;j--)
		    {
			    m[j]=b[i]*a[j]+p;
			    p=0;
		     	p=m[j]/10;
		    	m[j]%=10;
		    }
		    if(p>0)
		    {
			    mstr=char(p+'0');
			    z=true;
		    }
		    for(k=1;k<=lenm;k++)
		    {
			    if(z||m[k]!=0) mstr+=char(m[k]+'0');
		    }
		    for(l=1;l<=len-i;l++)
		    {
			    mstr+="0";
	        }
	    	sum=PLUS(sum,mstr);
		}
	}
	z=false;
	for(i=0;i<sum.size();i++)
	{
		if(sum[i]!=0||z)
		{
			cout<<sum[i];
			z=true;
		}
	}
	if(!z) cout<<0;
	return 0;
}
string PLUS (string x,string y) 
{
	string ans;
	int a[5001],b[5001],c[5001];
	int i,j,k,l,p=0,len;
	for(i=0;i<x.size();i++) a[i+1]=x[i]-'0';
	for(j=0;j<y.size();j++) b[j+1]=y[j]-'0';
	len=max(i,j);
	if(i<len)
	{
		l=len;
		a[len]=a[i];
		a[i]=0;
		for(k=i-1;k>=1;k--)
		{
			a[l-1]=a[k];
			a[k]=0;
			l--;
		}
	}
	if(j<len)
	{
		l=len;
		b[len]=b[j];
		b[j]=0;
		for(k=j-1;k>=1;k--)
		{
			b[l-1]=b[k];
			b[k]=0;
			l--;
		}
	}
	for(i=len;i>=1;i--)
	{
		c[i]=a[i]+b[i]+p;
		p=0;
		if(c[i]>=10)
		{
			p=1;
			c[i]%=10;
		}
	}
	bool z=false;
	if(p==1)
    {
    	ans+="1";
	}
	for(i=1;i<=len;i++)
	{
		if(z||c[i]!=0)
		{
			ans+=char(c[i]+'0');
			z=true;
		}
	}
	if(!z) ans+="0";
	return ans;
}