提交链接

题目描述：给出两个非负整数，求它们的乘积。

#include<bits/stdc++.h>
using namespace std;
#define N 2001
char a[N],b[N];
int c[2*N];
int main()
{
	int lena,lenb,lenc,carry=0;
	cin>>a>>b;
	
	lena = strlen(a);
	lenb = strlen(b);
	lenc = lena + lenb;
	
	if(strcmp(a,"0")==0 || strcmp(b,"0")==0)
	{
		cout<<"0";
		return 0;
	}
	else if(strcmp(a,"1")==0)
	{
		cout<<b<<endl;
		return 0;
	}
	else if(strcmp(b,"1")==0)
	{
		cout<<a<<endl;
		return 0;
	}
	
	for(int i=lena-1,p=0;i>=0;i--,p++)
		for(int j=lenb-1,q=0;j>=0;j--,q++)
		{
			c[p+q] += (a[i] - '0') * (b[j]-'0');
		}
	
	for(int i=0;i<lenc;i++)
	{
		c[i] += carry;
		carry = c[i]  / 10;
		c[i] = c[i]%10;
	}
	
	if(c[lenc-1]==0)lenc--;
	
	for(int i=lenc-1;i>=0;i--)
		cout<<c[i];
	cout<<endl;
	
	
	
	return 0;
}

根据题目分析，必然要使用高精度算法。
首先确定乘积后的位数。2位数成3位数，最小是10*1000结果是4位数
最大是99*999，cout发现是：98901,是一个5位数。所以乘积的位数在lena+lenb-1,lena+lenb之间

其次，确定每一位的值，以1234*567为例，计算过程如下：
                      1        2        3        4
                               5        6        7
------------------------------------------------------------
                    7*1      7*2      7*3      7*4
           6*1      6*2      6*3      6*4       
  5*1      5*2      5*3      5*4

从右往左编号。第0位是b[0]*a[0]
            第1位是b[0]*a[1] + b[1]*a[0]
            第2位是b[0]*a[2] + b[1]*a[1] + b[2]*a[0]
            ... ... 
            第5位是b[2]*a[3]

因此，c[i] =  b[j][i-j]    j={0,1,2,...i}

计算机出数组c后，统一进位，再去掉前导灵即可。 


测试没有问题，开始考虑特殊情况：
* A B有等于0的情况
* A B有等于1的情况