高精度

存储

• vector 数组
• 最低位在最左，最高位在最右

相当于 $\sum_{i=0}^n (a_i \times 10^i)$

1234 -> {4, 3, 2, 1}

输入输出

倒过来就行

void input(vector<int> &a){
    string s;
    cin >> s;
    // 从字符串末尾开始读
    for(int i = s.size() - 1;i >= 0;i--) 
        a.push_back(s[i] - '0');
}

void output(vector<int> a){
    // 从vector末尾开始输出
    for(int i = a.size() - 1;i >= 0;i--) cout << a[i];
    cout << endl;
}

加法

步骤

• 从低到高同位相加
• 从低到高依次进位
• 头部若有进位，则在最高位添1

代码

vector<int> add(vector<int> a, vector<int> b){
    // 取较大的长度
    int len = max(a.size(), b.size());
    vector<int> res;
    for(int i = 0;i < len;i++){
        // a或b长度不足时视为0
        if(i >= a.size()) res.push_back(b[i]);
        else if(i >= b.size()) res.push_back(a[i]);
        // 否则正常相加
        else res.push_back(a[i] + b[i]);
    }
    for(int i = 0;i < res.size();i++){
        // >=10时需要进位
        if(res[i] >= 10){
            // 当前数取个位
            res[i] %= 10;
            // 如果不是最后一位，直接在下一位加1
            if(i < res.size() - 1) res[i+1]++;
            // 否则在末尾添加一位1
            else res.push_back(1);
        }
    }
    return res;
}

乘法

步骤

• 两个数的长度相加得到结果最大长度
• 按位相乘，并加到结果对应位，并直接进位
• 去掉前导0

代码

vector<int> mul(vector<int> a, vector<int> b){
    // 结果长度最多为两个数长度之和（10^n * 10^m = 10^(n+m)）
    int len = a.size() + b.size();
    vector<int> res(len, 0);
    // 遍历两数的每一位
    for(int i = 0;i < a.size();i++){
        for(int j = 0;j < b.size();j++){
            // 当前位乘积加到结果对应位（10^i * 10^j = 10^(i+j)）
            res[i+j] += a[i] * b[j];
            // 进位，最多进1位（9 * 9 = 81）
            // i + j <= len - 2，不会越界
            res[i+j+1] += res[i+j] / 10;
            res[i+j] %= 10;
        }
    }
    // 去除高位多余的0
    while(!res.empty() && res.back() == 0) res.pop_back();
    return res;
}

取模

原理

• 整体取模前，先对因子取模没有影响 $(a × 10 + b) \space\% \space m = \bigg[(a\space \%\space m) × 10 + b\bigg]\space \%\space m$
• $res = (res \times 10 + a_i)$ 循环得到 $res$ 是 $a$ 存储的值
• 最高位被 $\times 10n$ 次，越低位被 $\times 10$ 的次数越少

{1,2,3,4} $\rightarrow 0 \times 10 + 4$ $\rightarrow 4 \times 10 + 3$ $\rightarrow 43 \times 10 + 2$ $\rightarrow 432 \times 10 + 1$ $\rightarrow 4321$

• 每次都对 $modn$ 取模，对结果无影响，还能防止溢出
• $res = (res * 10 + a[i]) \% modn$ 循环得到 $res$ 是 $a$ 存储的值 $\% modn$

ll mod(vector<int> a, ll modn){
    ll res = 0;
    for(int i = a.size() - 1;i >= 0;i--){
        // 从高位开始，每次乘10加当前位取模
        res = (res * 10 + a[i]) % modn;
    }
    return res;
}