A*B Problem

題目描述

給出兩個(gè)非負(fù)整數(shù)，求它們的乘積。

輸入格式

輸入共兩行，每行一個(gè)非負(fù)整數(shù)。

輸出格式

輸出一個(gè)非負(fù)整數(shù)表示乘積。

樣例 #1

樣例輸入 #1

1 
2

樣例輸出 #1

2

提示

每個(gè)非負(fù)整數(shù)不超過(guò) $10^{2000}$。

---

思路

通過(guò)兩層循環(huán)，將字符串 sa 和 sb 轉(zhuǎn)換為數(shù)字后逐位相乘，將乘法結(jié)果的當(dāng)前位存儲(chǔ)在 ic 數(shù)組的對(duì)應(yīng)位置中，將進(jìn)位加到 ic 數(shù)組的下一位。

注意：

1. 必須去除前導(dǎo)零，否則會(huì)導(dǎo)致WA。
2. ic 數(shù)組的低位存儲(chǔ)的是結(jié)果數(shù)值的高位。
3. 結(jié)果可能為 0，當(dāng) sc 為空字符串時(shí)直接輸出 0。

---

AC代碼

#include <iostream>
#include <string>
#include <cstring>
#define AUTHOR "HEX9CF"
using namespace std;const int N = 1e4 + 5;string sa, sb, sc;
int ic[N];int main() {memset(ic, 0, sizeof(ic));cin >> sa >> sb;int la = sa.length();int lb = sb.length();for(int i = la - 1; i >= 0; i--) {for(int j = lb - 1; j >= 0; j--) {int mul =  (sa[i] - '0') * (sb[j] - '0');int sum = mul + ic[i + j + 1];ic[i + j + 1] = sum % 10;ic[i + j] += sum / 10;}}sc = "";for(int i = 0; i < la + lb; i++) {if(sc.empty() && !ic[i]) {continue;}sc += to_string(ic[i]);}if(sc.empty()) {cout << 0 << endl;} else {cout << sc << endl;}return 0;
}