16.9 大數乘法
壓軸：大數乘法。關鍵問題是——A[i] 乘 B[j] 的結果，該記到答案的哪一位？
用位值想（16.1）：A[i] 的位值是 10^i、B[j] 的位值是 10^j，相乘的位值是 10^i \times 10^j = 10^{i+j}（又是指數律）。所以：
「歸戶」就是記帳的意思——每筆乘積像一筆錢，匯進「第 i+j 位」這個帳戶累加。兩層迴圈把所有 (i, j) 組合都乘一遍、各自歸戶，先不進位；全部累加完，最後用 16.8 的統一進位一次收拾。這比「邊乘邊進位」好寫得多——乘的階段只管記帳，進位的程式碼跟加法共用同一段。
拿 45 \times 67 走一遍（A = {5, 4}、B = {7, 6}）：
| 格子 | 收到的貢獻 | 累加結果 |
|---|---|---|
C[0] |
5 \times 7 | 35 |
C[1] |
5 \times 6 + 4 \times 7 | 58 |
C[2] |
4 \times 6 | 24 |
C[3] |
（先開著等進位） | 0 |
統一進位：35 留 5 進 3；58 + 3 = 61 留 1 進 6；24 + 6 = 30 留 0 進 3；最後一格收下 3。陣列成了 {5, 1, 0, 3}，倒著印是 3015——驗算 45 \times 67 正是 3015。
答案要開幾格？n 位數乘 m 位數，乘積最多 n + m 位（n 位數小於 10^n、m 位數小於 10^m，乘積小於 10^{n+m}），所以 C 開 n + m 格；位數少用不完的高位，交給 16.8 那套去前導零收尾。
¶完整程式
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> toDigits(const string& s) {
int len = s.size();
vector<int> d(len);
for (int i = 0; i < len; i++) {
d[i] = s[len - 1 - i] - '0';
}
return d;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string a, b;
cin >> a >> b;
vector<int> A = toDigits(a);
vector<int> B = toDigits(b);
int n = A.size(), m = B.size();
vector<long long> C(n + m, 0); // 乘積最多 n + m 位；累加用 long long
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
C[i + j] += (long long)A[i] * B[j]; // 位值 10^i × 10^j = 10^(i+j)：歸戶到第 i+j 位
}
}
for (int i = 0; i + 1 < (int)C.size(); i++) { // 統一進位（同 16.8）
C[i + 1] += C[i] / 10;
C[i] %= 10;
}
while (C.size() > 1 && C.back() == 0) C.pop_back(); // 去前導零
for (int i = (int)C.size() - 1; i >= 0; i--) cout << C[i];
cout << '\n';
return 0;
}
執行結果（輸入 12345 與 654321）：
8077592745¶這樣會不會太慢？
兩層迴圈，運算次數是 n \times m 次乘加。競程慣用 O(nm) 這種記號描述「跟 n \times m 成正比」的運算量級（O 記號見 10.1，這是 O(n^2) 的雙變數版本；正式的複雜度分析屬 Level 1 以上，這裡先看得懂就好）。兩個 4 \times 10^4 位的數相乘就是 1.6 \times 10^9 次基本運算，用上冊 4.9 的估算法貼著紅線；但每次只是一個乘法加一個加法，本站實測約一秒出頭，撐得進大數乘法題的時限。位數再往上，這個寫法就會吃緊——那是更進階演算法的地盤，Level 0 到 O(nm) 為止。
動手試試看：解掉大數乘法——就是本節的程式。提交前自我檢查三件事：累加陣列是不是 long long、有沒有去前導零、0 乘任何數印出來是不是單獨一個 0。