蓝桥杯备战（AcWing算法基础课）-高精度-乘-低精度

目录

前言

1 题目描述

2 分析

2.1 关键代码

2.2 关键代码分析

3 代码

---

前言

详细的代码里面有自己的理解注释

1 题目描述

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

输入格式

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

输出格式

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

数据范围

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

输入样例：

123
12

输出样例：

1476

2 分析

这个题和前面对高精度-加-高精度和高精度-减-高精度的分析有细微差别，因为前面的加减法都是高精度和高精度的运算，这题是高精度和低精度的运算，所以只要对A用先采用string存储，然后换成int数字，并且按照数组下标的低位存储数值低位存储数值，B采用int存储，即可。

2.1 关键代码

//C = A * b
vint mult1(vint &A,int b) {vint C;int t = 0;for(int i = 0; i < A.size(); i ++) {//相当于//    1 2 3//  *   1 2//  = 36 * 10^0 + 24 * 10^1 + 12 * 10^2 = 1476//  进位初始 t0 = 0//  3 * 12 + t0 = 36 + 0 = 36 ，保留 6 ，进位 t1 = 3//  2 * 12 + t1 = 24 + 3 = 27 ，保留 7 ，进位 t2 = 2//  1 * 12 + t2 = 12 + 2 = 14，保留 4 ，进位 t3 = 1// = (36%10 + t0)*10^0 + (24%10 + t1)*10^1 + (12%10 + t2)*10^2 + t3*10^3// = (6 + 0 ) * 10^0   + (4 + 3) * 10^1    + (2 + 2) * 10^2    + 1 * 10^3 = 1476//最后有个进位//	6 * 10^0 + (4 + 3) * 10^1 + (2 + 2) * 10^2 + 1 * 10^3= 1476t = A[i] * b + t;C.push_back(t % 10);t  = t / 10;}
//	if(t){
//		C.push_back(t);
//	}
//不能用 if(t) ，必须使用 while(t) 因为最后可能 t 不止 1 位
//比如 99 * 99 = 9801 ，最后 t = 98 ，如果用 if(t) ，实际上 C = [98,0,1] ，而不是 [9,8,0,1]
//也可以不用下面的代码，在for循环里面改为 i < A.size() ||t，并且加上 if(i<A.size()) t = A[i]*b + twhile(t) {C.push_back(t%10);t = t / 10;}//记得去前导 0 while(C.size() > 1 && C.back() == 0) C.pop_back();return C;
}

2.2 关键代码分析

代码实现的乘法运算和平常我们做题的计算是不一样的，代码里面它是按照A的每位乘B存储的，这样其实也是对的，只是我们一般学的时候是两个数每位相乘再相加进位。当i<A.size()时，每位值结果为A[i]*B[i]%10，进位为A[i]*B[i]/10，其实理解起来比较简单，比如123*12，按平常我们的计算个位是3*2=6，十位由两个部分构成，1*3+2*2=7。而在代码里面我们直接用3*12=36，其中这个3*12的3先看作是个位，36的3就是1*3那部分，权重是10，6即是结果的个位；下一步2*12=24，其中这个2*12的2先看作是十位，24的2权重是100，4就是2*2那部分，也就是十位，所以十位就是3+3=7，百位的进位为2，其他的依次类推即可。详细的计算说明，在上面的关键代码里面有

3 代码

#include<iostream>
#include<vector>using namespace std;
typedef long long LL;
typedef vector<int> vint;const int N = 1e5 + 10;//C = A * b
vint mult1(vint &A,int b) {vint C;int t = 0;for(int i = 0; i < A.size(); i ++) {//相当于//    1 2 3//  *   1 2//  = 36 * 10^0 + 24 * 10^1 + 12 * 10^2 = 1476//  进位初始 t0 = 0//  3 * 12 + t0 = 36 + 0 = 36 ，保留 6 ，进位 t1 = 3//  2 * 12 + t1 = 24 + 3 = 27 ，保留 7 ，进位 t2 = 2//  1 * 12 + t2 = 12 + 2 = 14，保留 4 ，进位 t3 = 1// = (36%10 + t0)*10^0 + (24%10 + t1)*10^1 + (12%10 + t2)*10^2 + t3*10^3// = (6 + 0 ) * 10^0   + (4 + 3) * 10^1    + (2 + 2) * 10^2    + 1 * 10^3 = 1476//最后有个进位//	6 * 10^0 + (4 + 3) * 10^1 + (2 + 2) * 10^2 + 1 * 10^3= 1476t = A[i] * b + t;C.push_back(t % 10);t  = t / 10;}
//	if(t){
//		C.push_back(t);
//	}
//不能用 if(t) ，必须使用 while(t) 因为最后可能 t 不止 1 位
//比如 99 * 99 = 9801 ，最后 t = 98 ，如果用 if(t) ，实际上 C = [98,0,1] ，而不是 [9,8,0,1]
//也可以不用下面的代码，在for循环里面改为 i < A.size() ||t，并且加上 if(i<A.size()) t = A[i]*b + twhile(t) {C.push_back(t%10);t = t / 10;}//记得去前导 0 while(C.size() > 1 && C.back() == 0) C.pop_back();return C;
}int main() {string a;int b;cin>>a>>b;//a = "123",b = 12vint A;//A=[3 , 2 , 1]，因为可能需要进位，个位放数组低位方便在数组高位加上进位for(int i = a.size() - 1 ; i >= 0 ; i --) {A.push_back(a[i] - '0');}if(b == 0) {cout<<0;} else {vint C = mult1(A,b);for(int i = C.size() - 1 ; i >= 0 ; i --) {cout<<C[i];}//cout<<C.size();}return 0;
}