16.7 當 long long 也裝不下：大數

上一節的結尾埋了顆雷：10^{18} 等級的數，long long 接得住；那100 位數呢？上冊 2.3 的型態表到 long long（19 位）就完了，C++ 沒有更大的內建整數型態——換型態這條路，到頭了。

但你在小學就見過答案。人類算 987 + 456 從來不是「一口吞下整個數」，而是一位一位算，滿十進位——直式運算根本不在乎數字有幾位，列得下就算得完。程式也一樣：別把數字塞進單一變數，改用「一格存一位」的陣列，用迴圈模擬直式運算。

位數多到內建型態裝不下的數，競程稱為大數（big number）。它的出場場合：部分 APCS 題、明確要求「精確的十進位答案」的題目——這種數當然也不能用 double 存（9.6 說過，double 超過 2^{53} 連整數都存不準，而大數要的就是每一位都精確）。

¶標準存法：個位住在索引 0

大數以字串讀入（10.7），再搬進 vector<int>（10.2），慣例把個位放在索引 0——也就是說，儲存順序跟人類的書寫順序相反：

數字（人類寫法）  ：3072                 高位在左、個位在右
string s          ："3072"               s[0]='3'……跟書寫同向，高位在前
vector<int> d     ：{2, 7, 0, 3}         d[0]=2 是個位——反向存！

為什麼要反著存？兩個理由，都跟直式運算的習性有關：

1. 直式運算從個位算起，而且兩數要「個位對齊」——個位都住索引 0，位數不同的兩個數對齊得毫不費力，d[i] 的位值也永遠是 10^i，跟 16.1 的定義完美對上。
2. 進位會讓數字變長，而長的方向是高位——高位住在尾端，變長就 push_back（10.2）；要是高位放前面，每次變長都得整串往後搬。

轉換程式就幾行（8.2 的 - '0' 又立功了）：

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

// 把字串形式的非負整數，轉成「個位住在索引 0」的數字陣列
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';   // s 的尾端（個位）放進 d[0]
    }
    return d;
}

int main() {
    string s = "3072";
    vector<int> d = toDigits(s);
    for (int i = 0; i < (int)d.size(); i++) {
        cout << "d[" << i << "] = " << d[i] << '\n';
    }
    return 0;
}

執行結果：

d[0] = 2
d[1] = 7
d[2] = 0
d[3] = 3

動手試試看：改寫本節程式——讀入一個數字字串，輸出它的位數、個位與最高位（位數就是 s.size()，個位是 d[0]，最高位是 d 的尾端）。拿一個 30 位的數字試跑，體會一下「long long 裝不下，但陣列毫無壓力」。