企业官网建设流程全解析

题目链接：

P1303 A*B Problem - 洛谷

这是高精乘法模板题目

#include<bits/stdc++.h> using namespace std; int main() { string s1,s2; cin >> s1 >> s2; if(s1 == "0" || s2 == "0") { cout << 0; return 0; } int n = s1.size(),m = s2.size(); vector<int> ans(n + m); for(int i = 0;i < n;i++) for(int j = 0;j < m;j++) ans[i+j] += (s1[n-1-i] - '0')*(s2[m-1-j] - '0'); for(int i = 0;i < n+m-1;i++) { ans[i+1] += ans[i] / 10; ans[i] %= 10; } int top = n + m - 1; while(ans[top] == 0) top--; for(int i = top;i >= 0;i--) cout << ans[i]; return 0; }

首先

a的位数是n b的位数是m

那么a*b结果位数不大于 n+m

原因是位数本质上等于“这个数在 10 的幂之间哪一格”：

• n 位数的范围：10^(n-1) ≤ A < 10^n
• m 位数的范围：10^(m-1) ≤ B < 10^m

两边相乘：

plaintext

10^(n+m-2) ≤ A×B < 10^(n+m)

所以A×B的范围是：

• 下界10^(n+m-2)是一个n+m-1位数（因为 10ᵏ 是 k+1 位数）
• 上界10^(n+m)是n+m+1位数，但注意是A×B < 10^(n+m)（严格小于），所以A×B最多是10^(n+m) − 1，那是n+m位数。

结论：A×B的位数在n+m-1到n+m之间，取最大就是n+m。

接着就是模拟我们手动乘法的过程：

哪一位和哪一个相乘，落在哪一位....

唯一不同的是我们算出的是每一位乘后的和

之后再同一的进位处理就好了