大數乘小整數題解

簡潔題意

給一個最多 \(10^5\) 位的非負整數 \(x\) 與一個 \(0 \le m \le 10^9\) 的整數，輸出 \(x \times m\)。

解法

這題是大數加法（15.8）與大數乘法（15.9）之間的踏腳石：乘數只有一個，所以不需要兩層迴圈的歸戶，但進位的處理已經跟乘法一樣。

把 \(x\) 轉成「個位住在索引 \(0\)」的反向陣列 A（15.7）之後：

逐位乘：C[i] += A[i] * m。位值不變（第 \(i\) 位乘上一個整數，還是第 \(i\) 位），所以不用歸戶到別的格子。
統一進位：C[i + 1] += C[i] / 10; C[i] %= 10;
去前導零、倒著印：跟加法完全一樣。

兩個跟加法不一樣的地方

第一，累加陣列要開 long long。 A[i] * m 最大是 \(9 \times 10^9\)，int 只到約 \(2.1 \times 10^9\)，直接溢位。

第二，進位不再只有 \(0\) 或 \(1\)。 加法時一格最多 \(9 + 9 = 18\)，往上送的進位只可能是 \(1\)，所以有人習慣寫成「超過 \(10\) 就減 \(10\)、往上加 \(1\)」。這裡一格是 \(9 \times 10^9\)，往上送的進位上看 \(9 \times 10^8\)——一定要用 C[i] / 10 算進位、C[i] % 10 留下本位。

答案有幾位

\(x\) 有 \(n\) 位、\(m\) 最多 \(10\) 位，乘積最多 \(n + 10\) 位，所以 C 開 n + 11 格綽綽有餘；用不到的高位交給去前導零收尾。

常犯錯誤

累加陣列開 int。\(9 \times 10^9\) 溢位。範例 3 會抓到這個錯。
把進位當成只會是 \(0\) 或 \(1\)（沿用加法的 if (C[i] >= 10) { C[i] -= 10; C[i+1]++; }）。範例 1 就會抓到這個錯。
忘記去前導零。多開的高位是 \(0\)，會印出一堆前導零；\(m = 0\) 時更是整串都是 \(0\)。範例 1 與範例 2 都會抓到這個錯。
去前導零去過頭，\(m = 0\) 時印出空字串。條件要保底至少留一位。

參考程式碼

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 把字串形式的非負整數，轉成「個位住在索引 0」的數字陣列（15.7）
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;
    long long m;
    cin >> a >> m;

    vector<int> A = toDigits(a);
    int n = A.size();

    // m 最多 10 位，乘積最多 n + 10 位
    vector<long long> C(n + 11, 0);
    for (int i = 0; i < n; i++) {
        C[i] += (long long)A[i] * m;      // 位值不變，不用歸戶到別的格子
    }
    for (int i = 0; i + 1 < (int)C.size(); i++) {
        C[i + 1] += C[i] / 10;            // 統一進位；進位可能遠大於 1
        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;
}

複雜度：\(O(n)\)。

大數乘小整數 題解