题目描述

给定两个正整数A和B，请你计算A * B的值。

样例

2
3

6

算法

(枚举)

1. 这里不管b是几位数，都是拿A的每一位直接乘整个b的
2. t表示进位，会出现进位大于10的情况，可能是11。这种情况，就要对t进行处理，将它放入C中。下面来看个栗子——
3. 如果在for()循环中，当然也会出现t = 11这一类的情况，但是因为是会进位的，所以不用担心。

输入样例

241879958093447809818753948872
48

这里在计算的时候，t就等于11，所以一定要用while来处理。不然会报错。之所以t会大于10，我猜测是因为大整数乘法，再加上进位这些，就很有可能了。(: 不知道对不对。。逃

while(t)
{
    C.push_back(t % 10);
    t /= 10;
}

时间复杂度

$O(n)$

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for(int i = 0; i < A.size(); i ++)  // **2
    {
        // 当A还没遍历完的时候就执行 t += A * b
        t += A[i] * b;  // **1     
        C.push_back(t % 10);
        t /= 10;
    }


    while(t)
    {
        C.push_back(t % 10);
        t /= 10;
    }

    while(C.size() > 1 && C.back() == 0) C.pop_back();

    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]);
}