大數乘法（困難版）題解

簡潔題意

給兩個最多 \(4 \times 10^4\) 位、沒有前導零的非負整數 \(x\) 與 \(y\)，輸出 \(x \times y\)。跟非困難版的差別只有一個：時限 \(0.25\) 秒。

解法

每位一格為什麼不夠用

15.9 的大數乘法（也就是課堂版大數乘法的做法）每位一格，歸戶要跑滿 \(n \times m\) 次。這題 \(40000 \times 40000 = 1.6 \times 10^9\) 次——本站實測要 \(1.1\) 秒，\(0.25\) 秒的時限就是衝著它來的。

壓位：一格存 6 位

省時間的方向不是換演算法，而是換進制：把數字改寫成 \(10^6\) 進制——由右往左每 \(6\) 個字元切成一格（跟 15.2 二進制轉十六進制「從右往左每 \(4\) 位一組」是同一件事），每格放 \(0 \sim 999999\)。位值系統的規則不因進制而變（15.1），所以 15.9 的歸戶、15.8 的統一進位整套照搬，只是 \(10\) 全換成 \(10^6\)：

C[i + j] += A[i] * B[j];      // 歸戶：位值 BASE^i × BASE^j = BASE^(i+j)
C[i + 1] += C[i] / BASE;      // 統一進位
C[i] %= BASE;

格數縮成 \(\frac{1}{6}\)，兩層迴圈的次數縮成 \(\frac{1}{36}\)：\((40000 / 6)^2 \approx 4.5 \times 10^7\) 次，本站實測 \(0.04\) 秒。

為什麼是 6 位

這是 15.6 那套估算的實戰：歸戶的單格累加上看「格數 \(\times\) 單筆乘積」\(\approx 6700 \times (10^6)^2 = 6.7 \times 10^{15}\)，long long（約 \(9.2 \times 10^{18}\)）撐得住。貪心壓到 \(8\) 位就翻車了：\(5000 \times (10^8)^2 = 5 \times 10^{19}\)，溢位。壓位的甜蜜點就是「格子越大迴圈越少，但單格累加不能爆」。

輸出的新坑

以格為單位去掉前導零之後，最高格照常印，其餘每格都要補滿 \(6\) 位。拿 \(1000000 \times 1\) 想：格子是 \(\{0, 1\}\)，最高格印 1，低位那格的 \(0\) 要印成 000000，答案才是 1000000——直接印 0 會輸出 10。低位格裡的前導零是位值的一部分，少印一個就整個錯位。

常犯錯誤

沿用每位一格（TLE）：\(1.6 \times 10^9\) 次歸戶，\(0.25\) 秒做不完
中間格沒補滿 \(6\) 位（WA）：低位格的值不足 \(6\) 位時，前導零是位值的一部分，不能省
壓 \(8\) 位、\(9\) 位（WA）：單格累加爆 long long——小測資抓不到，位數夠多才爆，最難查
切格子從左往右切（WA）：位數不是 \(6\) 的倍數時位值全錯，跟二進制轉十六進制沒左補 \(0\) 是同一個錯

參考程式碼

#include <iostream>
#include <string>
#include <vector>
using namespace std;

const long long BASE = 1000000;   // 一格存 6 位：把數字當成 10^6 進制

// 由右往左每 6 個字元切一格（個位那格住在索引 0）
vector<long long> toLimbs(const string& s) {
    vector<long long> d;
    for (int end = s.size(); end > 0; end -= 6) {
        int start = max(0, end - 6);
        long long v = 0;
        for (int i = start; i < end; i++) v = v * 10 + (s[i] - '0');   // 15.3 的累積式
        d.push_back(v);
    }
    return d;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string a, b;
    cin >> a >> b;
    vector<long long> A = toLimbs(a);
    vector<long long> B = toLimbs(b);
    int n = A.size(), m = B.size();

    vector<long long> C(n + m, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            C[i + j] += A[i] * B[j];          // 歸戶（同 15.9，基底換成 10^6）
        }
    }
    for (int i = 0; i + 1 < (int)C.size(); i++) {   // 統一進位（同 15.8）
        C[i + 1] += C[i] / BASE;
        C[i] %= BASE;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();   // 去前導零（以格為單位）

    cout << C.back();                          // 最高格照常印
    for (int i = (int)C.size() - 2; i >= 0; i--) {
        string t = to_string(C[i]);
        cout << string(6 - t.size(), '0') << t;   // 其餘每格補滿 6 位
    }
    cout << '\n';
    return 0;
}

複雜度：\(O\left(\frac{n}{6} \times \frac{m}{6}\right)\)。

大數乘法（困難版） 題解