【算法】【高精度】acwing算法基础 793. 高精度乘法

题目

给定两个非负整数（不含前导 0） A 和 B，请你计算 A×B 的值。

输入格式

共两行，第一行包含整数 A，第二行包含整数 B。

输出格式

共一行，包含 A×B 的值。

数据范围

1≤A的长度≤100000, 0≤B≤10000

输入样例： 2

3

输出样例：

6

来源：acwing算法基础 793. 高精度乘法

思路（注意事项）

• 去掉结果中的前导零:while (C.size() > 1 && C.back() == 0) C.pop_back();
• 注意函数mul()，循环条件中的t。

纯代码

#include<bits/stdc++.h>
using namespace std;

vector<int> mul(vector<int> A, int b)
{
	int t = 0;
	vector<int> C;
	for (int i = 0; i < A.size() || t; i ++)
	{
		if (i < A.size()) t += b * A[i];
		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 --) cout << C[i];
    
    return 0; 
}

题解（带注释）

#include<bits/stdc++.h>
using namespace std;

// 高精度乘法函数：计算一个大整数 A 和一个整数 b 的乘积
vector<int> mul(vector<int> A, int b) {
    int t = 0; // 进位标志
    vector<int> C; // 存储结果的数组

    // 逐位计算乘法
    for (int i = 0; i < A.size() || t; i++) {
        if (i < A.size()) t += b * A[i]; // 如果 A 还有位数，计算当前位的乘积并加上进位
        C.push_back(t % 10); // 将当前位的值存入结果数组
        t /= 10; // 计算进位
    }

    // 去掉结果中的前导零（如果结果不是 0）
    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--) cout << C[i];

    return 0;
}