第一种方法
第一种方法就是y总视频中讲的, 因为b较小可以被c++中的int表示, 因此我们将a*b拆解为a每一个数位上的数与b相乘, 组合而成答案
//
// Created by trudbot on 2022/7/5.
//
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
vector<int> eval(vector<int> a, int b)
{
vector<int> res;
int curr = 0;
for(int i : a)
{
curr += i * b;
res.push_back(curr % 10);
curr /= 10;
}
if(curr != 0) res.push_back(curr);
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
string a;
int b;
cin >> a >> b;
vector<int> va;
for(int i=a.length()-1; i>=0; i--) va.push_back(a[i]-'0');
vector<int> res = eval(va, b);
int last = res.size()-1;
while(last>0 && res[last] == 0) last--;
while(last>=0) cout << res[last--];
return 0;
}
第二种方法
第二种方法的适用性较强, 对任意长度的a和b均可使用.
以123*12举例, 将两个数从个位从0开始编号, 即
编号:2 1 0
1 2 3
1 2
按我们的习惯执行乘法
编号:2 1 0
1 2 3
1 2
----------
2 4 6
1 2 3
1 4 7 6
我们可以发现, 当a中编号为i的数与b中编号为j的数相乘时, 结果一定会加到i+j编号的位置, 以此原理我们的代码就很好写了
//
// Created by trudbot on 2022/7/4.
//
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<int, int> PII;
vector<int> multiply(vector<int> va, vector<int> vb)
{
vector<int> res;
int la = va.size(), lb = vb.size();
res.resize(la+lb-1);
for(int i=0; i<la; i++)
for(int j=0; j<lb; j++)
res[i+j] += va[i]*vb[j];
int carry = 0;
for(int i=0; i<=la+lb-2; i++)
{
res[i] += carry;
carry = res[i] / 10;
res[i] %= 10;
}
if(carry != 0) res.push_back(carry);
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
string a, b;
cin >> a >> b;
vector<int> va, vb;
for(int i=a.length()-1; i>=0; i--) va.push_back(a[i]-'0');
for(int i=b.length()-1; i>=0; i--) vb.push_back(b[i]-'0');
vector<int> res = multiply(va, vb);
int i = res.size()-1;
while(i>0 &&res[i] == 0) i--;
while(i >= 0) cout << res[i--];
return 0;
}