【6. 高精度乘法】

高精度乘法

思路：

• 高精度整数乘以低精度的整数，将较小的数看成整体，高精度整数的每一位，依次乘以低精度整数
• 下一位与小的整数相乘，并且再加上进位。
• 去掉前导0，因为结果可能是0123456

具体步骤

1. 将高精度整数A和低精度整数b倒序排放在数组中
2. 高精度整数的每一位，依次乘以低精度整数这个整体。
3. 考虑进位，(A * b + t) %10 为结果，(A * b + t) / 10为进位.
4. 去掉前导0，因为结果可能是0123456
5. 将C中数数字，倒序打印输出。

举例：

代码

#include <iostream>
#include <vector>
using namespace std;

vector<int> mul(vector<int> &A, int b)
{
   vector<int> C;
   int t = 0;         //最开始的t0 = 0;
   for (int i = 0; i < A.size() || t; i ++)
   {
       if(i < A.size()) t += A[i] * b;
       C.push_back(t % 10);
       t /= 10;
   }
   
   while (C.size() > 1 && C.back() == 0) C.pop_back();  //去掉前导0；
   return C;
}

int main()
{
   string a;
   int b;
   cin >> a >> b;
   
   vector<int>A;
   for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
   
   auto C = mul(A,b);
   
   for (int i = C.size() - 1; i >= 0; i --)printf("%d", C[i]);
}

核心算法可以改成：

vector<int> mul(vector<int> &A, int b)
{
   vector<int> C;
   int t = 0;         //最开始的t0 = 0;
   for (int i = 0; i < A.size() ; i ++)
   {
       t += A[i] * b;
       C.push_back(t % 10);
       t /= 10;                
   }                            
   if (t != 0) C.push_back(t);   //此时t有多种情况，可能为0（不进位），可能进位为1，也可能进位大于1
                                //加法这里只有俩种情况，要么进位,进位只进 1，要么不进位
   
   while (C.size() > 1 && C.back() == 0) C.pop_back();  //去掉前导0；
   return C;
}