P1303 A*B Problem

题目背景

高精度乘法模板题。

题目描述

给出两个非负整数，求它们的乘积。

输入格式

输入共两行，每行一个非负整数。

输出格式

输出一个非负整数表示乘积。

输入输出样例 #1

输入 #1

1 
2

输出 #1

2

说明/提示

每个非负整数不超过 。

题解

思路分析

1. python高精度解法

可以直接python一遍过

print(int(input())*int(input()))

python自带高精度，但是本题题意是要用高精度算法进行解题

2. C++高精度解法

对于以上例子，我们可以这样计算：

将2934和3489分别倒着存入两个数组a和b中：

用i遍历a数组作为外层循环，j遍历b数组作为内层循环，先进行逐个数位的相乘，例如；

之后再倒序输出即可。

具体计算过程

源文件：

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
#define lowbit(x) = ((x) & -(x))
#define rep_0(a, b, c) for (int a = b; a < c; a++)
#define per(a, b, c) for (int a = b; a >= c; a--)
using namespace std;

首先将两个特别大的数字读入字符串，然后倒着放进一维数组 （和高精度加法一样）：

    vector<int> a;
    vector<int> b;
    string s_a, s_b;
    cin >> s_a;
    cin >> s_b;
    int lena = s_a.size();
    int lenb = s_b.size();
    rep_0(i, 0, lena)
    {
        a.push_back(s_a[lena - i - 1] - '0');
    }
    rep_0(i, 0, lenb)
    {
        b.push_back(s_b[lenb - i - 1] - '0');
    }

接下来，不难想到，在计算乘法的时候可以使用两个循环进行枚举，以上面的图片为例子：外循环i为3489，内循环j为2934。 (你想想自己怎么算乘法的)

数组c作为答案数组，在枚举时令c[i+j-1]+=a[i] * b[j];

    vector<int> ans(lena + lenb, 0);
    for (int i = 0; i < lena; i++)
    {
        for (int j = 0; j < lenb; j++)
        {
            ans[i + j] += a[i] * b[j];
        }
    }

之后，我们只需要对c数组进行进位操作就好了。

    rep_0(i, 0, lena + lenb)
    {
        if (ans[i] > 9)
        {
            ans[i + 1] += ans[i] / 10;
            ans[i] = ans[i] % 10;
        }
    }

最后,我们还需要一个去除数字首多余的0的操作，同加法。

    int lenans = ans.size() - 1;
    per(i, ans.size() - 1, 0)
    {
        if (ans[i] == 0)
        {
            lenans--;
        }
        else
        {
            break;
        }
    }

最后的最后,我们只需要将数字输出就好了。

    if (lenans != -1)
    {
        per(p, lenans, 0) { cout << ans[p]; }
    }
    else
    {
        cout << 0;
    }

但是这里需要进行特判，如果ans里没有数字怎么办，例如0*125，这时就不会输出，所以加上特判，一切都完备了。

下提供完整AC代码。

AC代码

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
#define lowbit(x) = ((x) & -(x))
#define rep_0(a, b, c) for (int a = b; a < c; a++)
#define per(a, b, c) for (int a = b; a >= c; a--)
using namespace std;
void solve()
{
    vector<int> a;
    vector<int> b;
    string s_a, s_b;
    cin >> s_a;
    cin >> s_b;
    int lena = s_a.size();
    int lenb = s_b.size();
    rep_0(i, 0, lena)
    {
        a.push_back(s_a[lena - i - 1] - '0');
    }
    rep_0(i, 0, lenb)
    {
        b.push_back(s_b[lenb - i - 1] - '0');
    }
    vector<int> ans(lena + lenb, 0);
    for (int i = 0; i < lena; i++)
    {
        for (int j = 0; j < lenb; j++)
        {
            ans[i + j] += a[i] * b[j];
        }
    }
    rep_0(i, 0, lena + lenb)
    {
        if (ans[i] > 9)
        {
            ans[i + 1] += ans[i] / 10;
            ans[i] = ans[i] % 10;
        }
    }
    int lenans = ans.size() - 1;
    per(i, ans.size() - 1, 0)
    {
        if (ans[i] == 0)
        {
            lenans--;
        }
        else
        {
            break;
        }
    }
    if (lenans != -1)
    {
        per(p, lenans, 0) { cout << ans[p]; }
    }
    else
    {
        cout << 0;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;

    while (t--)
    {
        solve();
    }

    return 0;
}