高精度

高精度乘法

高精度乘低精度

// A 是大数（vector），b 是普通整数（int）
vector<int> mul(vector<int> &A, int b) {
    vector<int> C;
    int t = 0; // t 不仅是进位，也是当前计算的临时结果
    
    // 注意：这里的 t 可能很大，不仅仅是 0 或 1
    for (int i = 0; i < A.size() || t; i++) {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    
    // 去掉前导 0（比如 123 * 0 = 000，我们要变回 0）
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

高精度乘高精度

这个公式的证明其实非常直观，它的核心在于十进制数值的展开式。

我们可以通过以下三个步骤来证明：

1. 数值的数学表示

任何一个多位整数都可以写成以 $10$ 为底的幂级数形式。
假设大整数 $A$ 有 $n$ 位，大整数 $B$ 有 $m$ 位：

$$A = A[0] \cdot 10^0 + A[1] \cdot 10^1 + A[2] \cdot 10^2 + \dots + A[i] \cdot 10^i$$ $$B = B[0] \cdot 10^0 + B[1] \cdot 10^1 + B[2] \cdot 10^2 + \dots + B[j] \cdot 10^j$$

其中 $A[i]$ 是 $A$ 从右往左数第 $i$ 位上的数字（即权重为 $10^i$ 的位）。

2. 乘法的展开（多项式乘法）

当我们计算 $A \times B$ 时，根据乘法分配律，相当于 $A$ 中的每一项都要乘以 $B$ 中的每一项：

$$A \times B = \left( \sum_{i=0}^{n} A[i] \cdot 10^i \right) \times \left( \sum_{j=0}^{m} B[j] \cdot 10^j \right)$$

展开后的每一项可以写成：

$$(A[i] \cdot 10^i) \times (B[j] \cdot 10^j) = (A[i] \times B[j]) \cdot 10^{i+j}$$

3. 指数定律的运用

注意看结果中的幂次部分：

$$10^i \times 10^j = 10^{i+j}$$

这告诉我们：$A$ 的第 $i$ 位与 $B$ 的第 $j$ 位相乘的结果，其权重是 $10^{i+j}$。

在我们的结果数组 $C$ 中，$C[k]$ 存储的就是权重为 $10^k$ 的部分。因此，所有满足 $i + j = k$ 的乘积项 $(A[i] \times B[j])$ 都应该累加到 $C[k]$ 上。

---

举个简单的例子：$12 \times 34$

• $A = 12 = 1 \cdot 10^1 + 2 \cdot 10^0 \implies A[1]=1, A[0]=2$
• $B = 34 = 3 \cdot 10^1 + 4 \cdot 10^0 \implies B[1]=3, B[0]=4$

我们来算 $C[i+j]$：

1. 当 $i=0, j=0$：$i+j=0$。$C[0] = A[0] \times B[0] = 2 \times 4 = 8$
2. 当 $i=0, j=1$：$i+j=1$。$C[1] += A[0] \times B[1] = 2 \times 3 = 6$
3. 当 $i=1, j=0$：$i+j=1$。$C[1] += A[1] \times B[0] = 1 \times 4 = 4$（此时 $C[1] = 6+4=10$）
4. 当 $i=1, j=1$：$i+j=2$。$C[2] = A[1] \times B[1] = 1 \times 3 = 3$

目前 $C$ 数组为：{8, 10, 3}（对应 $8 \cdot 10^0 + 10 \cdot 10^1 + 3 \cdot 10^2$）

最后处理进位：

• $C[0]=8$
• $C[1]=10 \implies$ 留 $0$，进 $1$
• $C[2]=3 + 进位1 = 4$

结果为：$408$。 计算正确！

结论

这个公式的本质是：高精度乘法 = 多项式乘法 + 进位处理。
由于 $10^i \cdot 10^j = 10^{i+j}$，所以 $A[i] \cdot B[j]$ 必须且只能贡献给结果数组中的第 $i+j$ 位。

vector<int> mul_big(vector<int> &A, vector<int> &B) {
    vector<int> C(A.size() + B.size(), 0); // 结果长度最多是两者长度之和
    
    for (int i = 0; i < A.size(); i++) {
        for (int j = 0; j < B.size(); j++) {
            C[i + j] += A[i] * B[j];
        }
    }
    
    // 最后统一处理进位
    int t = 0;
    for (int i = 0; i < C.size(); i++) {
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }
    
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

洛谷1303

#include<bits/stdc++.h>

using namespace std;

  

vector<int> stringToV(string a){

    vector<int> n;

    int len=a.length();

    for(int i=len-1;i>=0;i--){

        int num=a[i]-'0';

        n.push_back(num);

    }

    return n;

}

  

vector<int> highMul(string s1,string s2){

    if(s1=="0" || s2=="0") return {0};

  

    vector<int> a=stringToV(s1);

    vector<int> b=stringToV(s2);

  

    vector<int> c(a.size()+b.size(),0);

    for(int i=0;i<a.size();i++){

        for(int j=0;j<b.size();j++){

            c[i+j]+=a[i]*b[j];

        }

    }

  

    int t=0;

    for(int i=0;i<c.size();i++){

        t+=c[i];

        c[i]=t%10;

        t/=10;

    }

  

    while(c.size()>1 && c.back()==0) c.pop_back();

    return c;

}

  

int main(){

    string a,b;

    cin>>a>>b;

    vector<int> ans=highMul(a,b);

    for(int i=ans.size()-1;i>=0;i--) cout<<ans[i];

    cout<<endl;

    return 0;

}

高精度加法

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

using namespace std;

// 高精度加法函数
vector<int> add(vector<int> &A, vector<int> &B) {
    vector<int> C;
    int t = 0; // t 代表进位

    for (int i = 0; i < A.size() || i < B.size(); i++) {
        // 如果 A 还没加完，就把 A[i] 加到 t
        if (i < A.size()) t += A[i];
        // 如果 B 还没加完，就把 B[i] 加到 t
        if (i < B.size()) t += B[i];
        
        C.push_back(t % 10); // 当前位的结果
        t /= 10;             // 计算新的进位
    }

    if (t) C.push_back(t);   // 最后如果还有进位，补上
    return C;
}

int main() {
    string s1, s2;
    cin >> s1 >> s2; // 读入两个巨大的数字

    vector<int> A, B;
    // 倒序存入 vector：'123' -> {3, 2, 1}
    for (int i = s1.size() - 1; i >= 0; i--) A.push_back(s1[i] - '0');
    for (int i = s2.size() - 1; i >= 0; i--) B.push_back(s2[i] - '0');

    vector<int> C = add(A, B);

    // 输出时也要倒着输出：{6, 5, 1} -> 156
    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    
    return 0;
}

高精度减法

要求 A >= B，核心是借位处理，(t + 10) % 10 这一行：t 为负时借位，加 10 取模得到当前位。

// 判断 A >= B
bool cmp(string a, string b) {
    if (a.size() != b.size()) return a.size() > b.size();
    return a >= b;
}

// 高精度减法（要求 A >= B）
vector<int> sub(vector<int>& A, vector<int>& B) {
    vector<int> C;
    int t = 0; // 借位
    for (int i = 0; i < A.size(); i++) {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

主函数里先判断大小：A >= B 直接减；否则交换两个数，输出时在前面加个负号。竞赛里甚至可以只留 sub 这一个函数。

字符串简化版（不依赖 vector，直接 string 操作）：

void exchange(string &a, string &b) {
    if (a.size() < b.size() || (a.size() == b.size() && a < b)) swap(a, b);
}

string sub(string a, string b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    string c; int t = 0;

    for (int i = 0; i < a.size(); i++) {
        t = a[i] - '0' - t;
        if (i < b.size()) t -= b[i] - '0';
        if (t < 0) { t += 10; c += char(t + '0'); t = 1; }
        else { c += char(t + '0'); t = 0; }
    }

    while (c.size() != 1 && c.back() == '0') c.pop_back();
    reverse(c.begin(), c.end());
    return c;
}

高精度除法（高精度 / 低精度）

从高位往低位做除法，余数 r 带上低一位继续除；结束后去掉前导 0。

// A / b，r 返回余数
vector<int> div(vector<int>& A, int b, int& r) {
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i--) {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

除法在四则运算里相对少见，但和高精乘（多项式乘法 + 统一进位）、高精减（借位）、高精加（进位）放在一起，一套四则运算就齐了。