所以直接用整数相乘,这条路是不通的,考虑间接的方法。

如果A用字符串{imageimage }表示,B用字符串{imageimage }表示呢,这样我们就将A*B的问题转化为字符串{imageimage }*{imageimage },

期望得到的结果也一定是类似于{C1…Cm+n}这样的字符串。

下面要做的事情就是如何得到C1…Cm+n了。

 

考虑以下公式:

A*B=A*{imageimage}=A*image*10^(m-1) + A*image *10^(m-2) +…+ A*image*10^0

也就是{C1…Cm+n}等于m个字符串相加(用一个循环可以实现),这m个字符串形式为A*image *10^(m-i);所以问题分解为以下两个目标

  1. m个字符串相加
    m个字符串相加可以转化为“两个字符串相加”
  2. 求形如A*image *10^(m-i)的乘积
    其中imageimage [0-9]
    而10^(m-i)就是在A*Bi后加(m-i)个0,问题进一步简化为求A*image字符串

下面我们求解点2

A*image={imageimage }*image=image*image*10^(n-1) + image *image*10^(n-2)+ …+ image*image*10^0

可见这里是n个字符串相加(用一个循环也可以实现),这n个字符串形式为image*image*10^(n-j);和上面类似,问题分解为以下两个目标

  1. n个字符串相加
  2. 求形如image*image*10^(n-j)的乘积
    其中imageimageimage [0-9]
    很显然image*image是最基本的运算,我们可以直接做到。

以下是bottoms,我们理解为base操作:

  1. 两个字符串相加
  2. image*image
    制作乘法表