/************************************************************************
Author: xiep
Date  : 2008-9-27
其实像大数乘法，加法，减法，阶乘问题常见算法是用数组或向量（vector）等模拟手算。
只考虑了非负数的情形。
测试用例考虑了大数乘大数，
              大数乘小数，
              小数乘大数，
              小数乘小数，
          以及0乘和乘0。
*************************************************************************/

#include <fstream>
#include <assert.h>
using namespace std;

#define	MAX_LEN	10000 + 1

void by(int res[],		//保存结果,顺序存储
		int num1[],		//被乘数,顺序存储
		int len1,		//被乘数位数
		int num2[],		//乘数,顺序存储
		int len2)		//乘数位数
{
	int i,j,k;			//循环变量
	int lenres=len1+len2;		//结果数组的长度

	//将结果数组初始化为0,这是必须的
	for(i=0; i<lenres; i++)
		res[i]=0;
	
	//构造一个大小等于被乘数的数组，用于保存中间结果
	int *temp = new int[len1];
	assert( NULL != temp );
	
	//关键代码
	int index=0;
	for(i=len2-1; i>=0; i--)		//乘数
	{
		index++;
		for(k=lenres-index,j=len1-1; j>=0; k--,j--)
		{
			temp[j] = num1[j]*num2[i];	//乘
			res[k] += temp[j];		//将中间结果加入结果数组
		}
	}
	delete[] temp;					//回收内存
	
	int tmp,carry=0;
	for (i=lenres-1; i>0; i--)
	{
		tmp = res[i]+carry;			//因为( (2^31-1) - (2^31-1)/10 ) / 81 = 50373073
		res[i] = tmp % 10;			//所以乘数最多可以是 50373073 位
		carry = tmp /10;            //被乘数位数不限，保证不溢出
	}
	res[0]=carry;
}


int main(void)
{
	fstream in( "in.txt" );
	fstream out( "out.txt" );

	char chNum1[MAX_LEN], chNum2[MAX_LEN];

	int testcaseNum;
	in>>testcaseNum;

	int i;
	while(testcaseNum--)
	{
		in>>chNum1>>chNum2;
		int len1 = strlen(chNum1);
		int len2 = strlen(chNum2);
		
		int intNum1[MAX_LEN],						//被乘数
			intNum2[MAX_LEN],						//乘数
			*result=new int[len1+len2];				//结果	
		assert( NULL != result);
		
		for(i=0; i<len1; i++)
			intNum1[i]=chNum1[i]-'0';

		for(i=0; i<len2; i++)
			intNum2[i]=chNum2[i]-'0';
		
		by(result,intNum1,len1,intNum2,len2);		//乘
		
		//输出结果
		bool remain0 = true;
		for(i=0; i<len2+len1; i++)
		{
			if( result[i] != 0 ) remain0 = false;
			if( !remain0 ) out<<result[i];
		}
		if( remain0 ) out<<"0";
		out<<endl;
		
		delete[] result;							//回收内存
	}
	
    return 0;
}

[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界