大数乘法

示例：

123456789123456789（18位） * 123456789123456789（18位）= ?15241578780673678515622620750190521（35位）

思想：我们来看一个例子，用例子来说明具体如果模拟大数乘法（如：123*45）。

? ? ? ? ? ? ? ?1 ? ? 2 ? ?3

? ? ? ? ?x ? ? ? ? ? 4 ? ?5

--------------------------------

? ? ? ? ? ? ? 5 ? ?10 ?15 ? ? ? ? ?（1、此行为：123 * 5）

? ? ? ?4 ? ? 8 ? ?12 ? ? ? ? ? ? ? ?（2、此行为：123 * 4）

---------------------------------

? ? ? 4 ? ? 13 ? 22 ?15 ? ? ? ? ?（3、将上面两行相加得到此行） ? ? ? ??

---------------------------------

? ? ? 5 ? ? ? 5 ? ?3 ? ? 5 ? ? ? ? ?（4、将上一行的大于9的数字进行进位处理，得到最终结果）

/*
	Title:大数乘法
	Author:Dojking
*/
#include <iostream>
#include <string>
using namespace std;

void BigMul(string mul1,string mul2)
{
	int i,j,t,k,len1,len2;

	len1 = mul1.size()-1;
	len2 = mul2.size()-1;
	t = k = len1+len2+2;      /*动态开辟空间大小计算*/

	int *strmul = new int[k]; /*开辟空间*/
	for (i = 0; i < k; ++i)   /*初始化为0*/
		strmul[i] = 0;

	for (j = len2; j >= 0; --j)/*核心代码：大数乘法*/
	{
		t = --k;
		for (i = len1; i >= 0; --i)
		{
			strmul[t] += (mul1[i]-'0') * (mul2[j]-'0');
			--t;
		}
	}

	for (i = len1+len2+1; i >= 0; --i) /*进位处理*/
	{
		if (strmul[i] >= 10)
		{
			strmul[i-1] += (strmul[i] / 10);
			strmul[i] %= 10;
		}
	}

	i = 0;
	while (strmul[i] == 0 && (i < len1+len2+1))/*跳过前面无效0，排除全部为0情况*/
		++i;
	for ( ; i <= len1+len2+1; ++i)     /*打印结果*/
		cout<<strmul[i];
	cout<<endl;
	delete[] strmul;     /*释放空间*/
	strmul = NULL;
}

int main()
{
	string mul1,mul2;

	cin>>mul1>>mul2;
	BigMul(mul1,mul2);  /*大数乘法*/

	return 0;
}