基础算法之高精度算法教学讲义

---

一、概念定义、价值意义

1.1 什么是高精度算法

高精度算法（High Precision Algorithm）：当参与运算的数值超出标准数据类型（int、long long）所能表示的范围时，使用数组或字符串来存储每一位数字，并模拟人工竖式计算的过程来完成运算的算法。

在 C++ 中，int 最大约 2.1×10⁹，long long 最大约 9.2×10¹⁸。当数值达到几十位、上百位甚至上千位时（如阶乘、大整数乘法），必须使用高精度技术。

1.2 价值意义

• 突破范围限制：可处理任意长度的整数（受内存限制）。
• 竞赛必考：NOIP、CSP-J/S 中高精度运算（加法、减法、乘法、除法、乘方）是常见考点。
• 基础工具：许多高级算法（如大数分解、RSA加密）依赖高精度。
• 理解计算机运算本质：通过模拟竖式计算，加深对进位、借位等底层机制的理解。

---

二、核心思想、算法原理、算法框架、图示解析

2.1 核心思想

将大整数以字符串或数字数组形式存储，每一位独立进行运算，并手动处理进位或借位。

• 存储方式：常用 vector<int> 存储，低位在数组前端（下标0是个位），便于进位扩展。
• 对齐方式：加法、减法、乘法时，从最低位（数组下标 0）开始逐位运算。

2.2 算法原理（七种运算）

（1）高精度加法（大数 + 大数）

逐位相加，若结果 ≥10 则进位，当前位保留 sum % 10。

（2）高精度减法（大数 - 大数，被减数 ≥ 减数）

逐位相减，若不够减则借位，当前位加 10 后再减，最后去除前导零。

（3）高精度乘法（大数 × 低精度整数）

逐位乘以低精度整数，加上进位，保留个位，进位继续传递。

（4）高精度乘法（大数 × 大数）

双重循环：将 a 的第 i 位与 b 的第 j 位乘积累加到结果的第 i+j 位，最后统一处理进位。

（5）高精度除法（大数 ÷ 低精度整数）

从高位向低位逐位处理：当前余数 = 上一位余数×10 + 当前位，商的一位 = 当前余数 ÷ 除数，新余数 = 当前余数 % 除数。

（6）高精度除法（大数 ÷ 大数）

模拟竖式除法：先比较被除数和除数大小，若被除数小则商为0；否则计算位数差 shift，将除数扩大 10^shift 倍，然后逐位试商，每次用当前余数减去试商倍数的除数，记录商的一位，然后除数右移一位，重复直到处理完所有位。

（7）高精度乘方（大数的整数次幂）

使用快速幂算法：将指数二进制分解，底数不断自乘，指数为奇数时累乘到底数，最终结果 = 底数^指数。

2.3 算法框架（中文伪代码）

（1）高精度加法（大数 + 大数）

函数 高精度加法(a, b):
    进位 = 0
    结果 = 空数组
    i = 0
    当 i < a的长度 或 i < b的长度 或 进位 != 0:
        和 = 进位
        如果 i < a的长度: 和 = 和 + a[i]
        如果 i < b的长度: 和 = 和 + b[i]
        结果.尾部添加(和 % 10)
        进位 = 和 / 10
        i = i + 1
    返回 结果逆序   // 得到高位在前的正常表示

（2）高精度减法（大数 - 大数，要求 a ≥ b）

函数 高精度减法(a, b):
    借位 = 0
    结果 = 空数组
    对 i 从 0 到 a的长度-1:
        差 = a[i] - 借位
        如果 i < b的长度: 差 = 差 - b[i]
        如果 差 < 0:
            差 = 差 + 10
            借位 = 1
        否则:
            借位 = 0
        结果.尾部添加(差)
    当 结果的长度 > 1 且 结果的最后一个元素 == 0:
        结果.弹出尾部元素
    返回 结果逆序

（3）高精度乘法（大数 × 低精度整数）

函数 高精度乘低精度(a, b):
    进位 = 0
    结果 = 空数组
    对 i 从 0 到 a的长度-1:
        积 = a[i] * b + 进位
        结果.尾部添加(积 % 10)
        进位 = 积 / 10
    当 进位 > 0:
        结果.尾部添加(进位 % 10)
        进位 = 进位 / 10
    返回 结果逆序

（4）高精度乘法（大数 × 大数）

函数 高精度乘高精度(a, b):
    初始化 结果 为长度为 a的长度+b的长度 的全0数组
    对 i 从 0 到 a的长度-1:
        对 j 从 0 到 b的长度-1:
            结果[i+j] = 结果[i+j] + a[i] * b[j]
    进位 = 0
    对 i 从 0 到 结果的长度-1:
        值 = 结果[i] + 进位
        结果[i] = 值 % 10
        进位 = 值 / 10
    当 结果的长度 > 1 且 结果的最后一个元素 == 0:
        结果.弹出尾部元素
    返回 结果逆序

（5）高精度除法（大数 ÷ 低精度整数）

函数 高精度除低精度(a, b):
    余数 = 0
    结果 = 空数组
    // 从高位向低位遍历
    对 i 从 a的长度-1 向下到 0:
        当前 = 余数 * 10 + a[i]
        结果.尾部添加(当前 / b)
        余数 = 当前 % b
    结果.逆序()   // 因为添加时是从高位到低位，现在逆序让低位在前
    当 结果的长度 > 1 且 结果的最后一个元素 == 0:
        结果.弹出尾部元素
    返回 (结果, 余数)

（6）高精度除法（大数 ÷ 大数）

函数 高精度除高精度(a, b):
    如果 a < b (调用比较函数):
        返回 (商=[0], 余数=a)
    偏移 = a的长度 - b的长度
    除数 = b 扩大 10^偏移 倍   // 末尾补零
    结果 = 空数组
    余数 = a
    对 i 从 偏移 向下到 0:
        计数 = 0
        当 余数 >= 除数:
            余数 = 余数 - 除数
            计数 = 计数 + 1
        结果.尾部添加(计数)
        除数 = 除数 除以 10   // 右移一位
    结果.逆序()   // 因为添加时是从高位到低位
    当 结果的长度 > 1 且 结果的最后一个元素 == 0:
        结果.弹出尾部元素
    返回 (结果, 余数)

（7）高精度乘方（大数的整数次幂）

函数 高精度乘方(底数, 指数):
    结果 = [1]   // 初始化为1
    当前 = 底数
    当 指数 > 0:
        如果 指数 % 2 == 1:
            结果 = 高精度乘高精度(结果, 当前)
        当前 = 高精度乘高精度(当前, 当前)
        指数 = 指数 / 2
    返回 结果

2.4 图示解析（中文）

（1）高精度加法图示

以 345 + 678 为例：

  下标(低位→高位)    2    1    0
        a:          3    4    5
        b:          6    7    8
       ─────────────────────────
第0步: 5+8=13 → 写3，进位=1
第1步: 4+7+1=12 → 写2，进位=1
第2步: 3+6+1=10 → 写0，进位=1
第3步: 进位1 → 写1
结果数组（低位在前）: [3,2,0,1]
逆序输出: 1 0 2 3 → 1023

（2）高精度减法图示

以 1023 - 678 为例（先确保被减数≥减数）：

  下标(低位→高位)    3    2    1    0
        a:          3    2    0    1
        b:          8    7    6    0
       ─────────────────────────────
第0步: 3-8 不够 → 13-8=5，借位=1
第1步: 2-7-借位1 → 2-8不够 → 12-8=4，借位=1
第2步: 0-6-借位1 → 0-7不够 → 10-7=3，借位=1
第3步: 1-0-借位1 = 0
结果数组（低位在前）: [5,4,3,0]
去除前导零 → [5,4,3]
逆序输出: 3 4 5 → 345

（3）高精度乘低精度图示

以 123 × 4 为例：

  下标(低位→高位)    2    1    0
        a:          1    2    3
        b:          4
       ─────────────────────────
第0步: 3×4=12 → 写2，进位=1
第1步: 2×4+1=9 → 写9，进位=0
第2步: 1×4+0=4 → 写4
结果数组（低位在前）: [2,9,4]
逆序输出: 4 9 2 → 492

（4）高精度乘高精度图示

以 123 × 45 为例：

       a = 123（存储为[3,2,1]）
       b = 45（存储为[5,4]）
   初始化结果数组长度=3+2=5，全0

   i=0(a[0]=3):
       j=0(b[0]=5): res[0] += 3*5=15
       j=1(b[1]=4): res[1] += 3*4=12
   i=1(a[1]=2):
       j=0: res[1] += 2*5=10 → res[1]=22
       j=1: res[2] += 2*4=8
   i=2(a[2]=1):
       j=0: res[2] += 1*5=5 → res[2]=13
       j=1: res[3] += 1*4=4

   未进位数组: [15,22,13,4,0]
   进位处理:
       i=0: val=15 → res[0]=5, carry=1
       i=1: val=22+1=23 → res[1]=3, carry=2
       i=2: val=13+2=15 → res[2]=5, carry=1
       i=3: val=4+1=5 → res[3]=5, carry=0
       i=4: val=0 → res[4]=0
   结果数组（低位在前）: [5,3,5,5,0]
   去除前导零 → [5,3,5,5]
   逆序输出: 5 5 3 5 → 5535? 实际123×45=5535，正确。

（5）高精度除低精度图示

以 12345 ÷ 12 为例：

   a = 12345（存储为[5,4,3,2,1]），从高位向低位处理：
   remainder=0
   第4位（最高位1）: cur=0×10+1=1 → 1/12=0, rem=1
   第3位（2）: cur=1×10+2=12 → 12/12=1, rem=0
   第2位（3）: cur=0×10+3=3 → 3/12=0, rem=3
   第1位（4）: cur=3×10+4=34 → 34/12=2, rem=10
   第0位（5）: cur=10×10+5=105 → 105/12=8, rem=9
   商的各位（从高位到低位）: [0,1,0,2,8]
   去除前导零 → [1,0,2,8]
   逆序输出商: 8 2 0 1? 注意存储：我们得到的是高位在前列表，反转后为低位在前？实际应直接输出高位到低位：1 0 2 8 → 1028，余数9。

（6）高精度除高精度图示

以 1024 ÷ 12 为例（简化理解）：

   a = 1024（存储[4,2,0,1]）
   b = 12（存储[2,1]）
   比较 a ≥ b，shift = 4-2=2
   除数扩大10^2倍 → 1200（存储[0,0,2,1]）
   i从2降到0:
       i=2: 除数=1200，余数初始为1024，1024<1200 → 商位0
       i=1: 除数右移一位→120，1024≥120？是，试商：1024-120=904(1次),904-120=784(2次)...直到小于120。实际试商8次（8×120=960），余数64。商位=8
       i=0: 除数右移一位→12，余数64≥12，试商5次（5×12=60），余数4，商位=5
   商的各位从高到低：0,8,5 → 85，余数4。
   即1024 ÷ 12 = 85 余 4。

（7）高精度乘方图示

以 2^10 为例（底数2，指数10）：

   底数 base = [2]
   指数 exp = 10，结果 res = [1]
   二进制：10 = 1010₂
   遍历二进制位（从低位到高位）：
       第一轮（exp%2=0）：cur = base×base = 2×2=4，exp=5
       第二轮（exp%2=1）：res = res×cur = 1×4=4，cur = 4×4=16，exp=2
       第三轮（exp%2=0）：cur = 16×16=256，exp=1
       第四轮（exp%2=1）：res = 4×256=1024，cur = 256×256=65536，exp=0
   结果 res = 1024，正确。

---

三、代码模型、代码模板

3.1 存储与输出

#include <bits/stdc++.h>
using namespace std;

// 字符串转 vector（低位在前）
vector<int> toVec(string s) {
    vector<int> res;
    for (int i = (int)(s.size()) - 1; i >= 0; i--) {
        res.push_back(s.at(i) - '0');
    }
    return res;
}

// 输出高精度数（从高位到低位）
void printVec(vector<int> &vec) {
    for (int i = (int)(vec.size()) - 1; i >= 0; i--) {
        cout << vec.at(i);
    }
    cout << endl;
}

3.2 高精度加法模板

vector<int> add(vector<int> &a, vector<int> &b) {
    vector<int> res;
    int carry = 0;
    int len = max((int)(a.size()), (int)(b.size()));
    for (int i = 0; i < len; i++) {
        int sum = carry;
        if (i < (int)(a.size())) sum += a.at(i);
        if (i < (int)(b.size())) sum += b.at(i);
        res.push_back(sum % 10);
        carry = sum / 10;
    }
    if (carry) res.push_back(carry);
    return res;
}

3.3 高精度减法模板（保证 a ≥ b）

vector<int> sub(vector<int> &a, vector<int> &b) {
    vector<int> res;
    int borrow = 0;
    for (int i = 0; i < (int)(a.size()); i++) {
        int diff = a.at(i) - borrow;
        if (i < (int)(b.size())) diff -= b.at(i);
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        res.push_back(diff);
    }
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    return res;
}

3.4 高精度乘法（大数 × 低精度整数）

vector<int> mulLow(vector<int> &a, int b) {
    vector<int> res;
    int carry = 0;
    for (int i = 0; i < (int)(a.size()); i++) {
        long long prod = (long long)a.at(i) * b + carry;
        res.push_back(prod % 10);
        carry = prod / 10;
    }
    while (carry) {
        res.push_back(carry % 10);
        carry /= 10;
    }
    return res;
}

3.5 高精度乘法（大数 × 大数）

vector<int> mulHigh(vector<int> &a, vector<int> &b) {
    vector<int> res(a.size() + b.size(), 0);
    for (int i = 0; i < (int)(a.size()); i++) {
        for (int j = 0; j < (int)(b.size()); j++) {
            res.at(i + j) += a.at(i) * b.at(j);
        }
    }
    int carry = 0;
    for (int i = 0; i < (int)(res.size()); i++) {
        int val = res.at(i) + carry;
        res.at(i) = val % 10;
        carry = val / 10;
    }
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    return res;
}

3.6 高精度除法（大数 ÷ 低精度整数）

vector<int> divLow(vector<int> &a, int b, int &rem) {
    vector<int> res;
    long long remainder = 0;
    for (int i = (int)(a.size()) - 1; i >= 0; i--) {
        remainder = remainder * 10 + a.at(i);
        res.push_back(remainder / b);
        remainder %= b;
    }
    rem = remainder;
    reverse(res.begin(), res.end());
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    return res;
}

3.7 高精度除法（大数 ÷ 大数）

bool greaterOrEqual(vector<int> &a, vector<int> &b) {
    if (a.size() != b.size()) return a.size() > b.size();
    for (int i = (int)(a.size()) - 1; i >= 0; i--) {
        if (a.at(i) != b.at(i)) return a.at(i) > b.at(i);
    }
    return true;
}

vector<int> sub(vector<int> &a, vector<int> &b) {
    vector<int> res;
    int borrow = 0;
    for (int i = 0; i < (int)(a.size()); i++) {
        int diff = a.at(i) - borrow;
        if (i < (int)(b.size())) diff -= b.at(i);
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        res.push_back(diff);
    }
    while ((int)(res.size()) > 1 && res.back() == 0) res.pop_back();
    return res;
}

vector<int> divHigh(vector<int> &a, vector<int> &b, vector<int> &rem) {
    vector<int> res;
    rem = a;
    if (!greaterOrEqual(a, b)) {
        res.push_back(0);
        return res;
    }
    int shift = (int)(a.size()) - (int)(b.size());
    vector<int> divisor = b;
    reverse(divisor.begin(), divisor.end());
    for (int i = 0; i < shift; i++) divisor.push_back(0);
    reverse(divisor.begin(), divisor.end());
    for (int i = shift; i >= 0; i--) {
        int cnt = 0;
        while (greaterOrEqual(rem, divisor)) {
            rem = sub(rem, divisor);
            cnt++;
        }
        res.push_back(cnt);
        if (i > 0) {
            divisor.erase(divisor.begin());
            while (divisor.size() > 1 && divisor.back() == 0) divisor.pop_back();
        }
    }
    reverse(res.begin(), res.end());
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    return res;
}

3.8 高精度乘方（快速幂）

vector<int> powHigh(vector<int> &base, int exp) {
    vector<int> res = {1};
    vector<int> cur = base;
    while (exp > 0) {
        if (exp & 1) {
            res = mulHigh(res, cur);
        }
        cur = mulHigh(cur, cur);
        exp >>= 1;
    }
    return res;
}

---

四、基本要素、基本方法、基本步骤

4.1 基本要素

要素	说明
存储结构	vector<int> 低位在前，便于进位扩展。
进位/借位	加法（carry），减法（borrow），乘法（逐位累加后统一进位）。
对齐方式	从低位（下标0）开始逐位运算。
前导零去除	运算后删除结果高位的多余零。

4.2 基本方法

1. 字符串输入转数组：倒序存储。
2. 比较大小（用于减法、除法）：先比长度，长度相同逐位比高位。
3. 加法：逐位加 + 进位。
4. 减法：逐位减 + 借位。
5. 乘法（大×小）：逐位乘 + 进位。
6. 乘法（大×大）：双重循环累加 + 统一进位。
7. 除法（大÷小）：逐位求商 + 余数传递。
8. 除法（大÷大）：模拟竖式，试商后相减。
9. 乘方：快速幂 + 高精度乘法。

4.3 基本步骤（以加法为例）

1. 读入两个大整数（字符串形式）。
2. 转换为 vector<int>（低位在前）。
3. 调用加法函数，逐位相加并处理进位。
4. 去除结果前导零。
5. 逆序输出。

---

五、经典例题（6题，含思路解析和详细注释）

例题1：A + B 高精度加法

题目描述

计算两个不超过 500 位的非负整数之和。

输入：两行，每行一个整数。 输出：它们的和。

思路解析

• 使用 vector<int> 存储两个数的低位在前形式。
• 逐位相加，用 carry 记录进位。
• 最后若仍有进位则添加。

代码实现

#include <bits/stdc++.h>
using namespace std;

vector<int> add(vector<int> &a, vector<int> &b) {
    vector<int> res;
    int carry = 0;
    int len = max((int)(a.size()), (int)(b.size()));
    for (int i = 0; i < len; i++) {
        int sum = carry;
        if (i < (int)(a.size())) sum += a.at(i);
        if (i < (int)(b.size())) sum += b.at(i);
        res.push_back(sum % 10);
        carry = sum / 10;
    }
    if (carry) res.push_back(carry);
    return res;
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    vector<int> a, b;
    for (int i = (int)(s1.size()) - 1; i >= 0; i--) {
        a.push_back(s1.at(i) - '0');
    }
    for (int i = (int)(s2.size()) - 1; i >= 0; i--) {
        b.push_back(s2.at(i) - '0');
    }
    vector<int> res = add(a, b);
    for (int i = (int)(res.size()) - 1; i >= 0; i--) {
        cout << res.at(i);
    }
    cout << endl;
    return 0;
}

例题2：A - B 高精度减法

题目描述

计算两个不超过 500 位的非负整数之差（被减数 ≥ 减数）。

输入：两行，每行一个整数（第一个 ≥ 第二个）。 输出：它们的差。

思路解析

• 确保被减数不小于减数（题目已保证）。
• 逐位相减，处理借位（borrow）。
• 去除结果前导零。

代码实现

#include <bits/stdc++.h>
using namespace std;

vector<int> sub(vector<int> &a, vector<int> &b) {
    vector<int> res;
    int borrow = 0;
    for (int i = 0; i < (int)(a.size()); i++) {
        int diff = a.at(i) - borrow;
        if (i < (int)(b.size())) diff -= b.at(i);
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        res.push_back(diff);
    }
    while ((int)(res.size()) > 1 && res.back() == 0) {
        res.pop_back();
    }
    return res;
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    vector<int> a, b;
    for (int i = (int)(s1.size()) - 1; i >= 0; i--) {
        a.push_back(s1.at(i) - '0');
    }
    for (int i = (int)(s2.size()) - 1; i >= 0; i--) {
        b.push_back(s2.at(i) - '0');
    }
    vector<int> res = sub(a, b);
    for (int i = (int)(res.size()) - 1; i >= 0; i--) {
        cout << res.at(i);
    }
    cout << endl;
    return 0;
}

例题3：高精度阶乘（n!）

题目描述

输入一个整数 n（n ≤ 1000），输出 n! 的精确值。

输入：一个整数 n。 输出：n!。

思路解析

• 使用高精度乘法（大数 × 低精度整数）。
• 初始结果 res = {1}。
• 从 2 循环到 n，每次将 res 与当前整数 i 相乘。

代码实现

#include <bits/stdc++.h>
using namespace std;

vector<int> mulLow(vector<int> &a, int b) {
    vector<int> res;
    int carry = 0;
    for (int i = 0; i < (int)(a.size()); i++) {
        long long prod = (long long)a.at(i) * b + carry;
        res.push_back(prod % 10);
        carry = prod / 10;
    }
    while (carry) {
        res.push_back(carry % 10);
        carry /= 10;
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<int> res = {1};
    for (int i = 2; i <= n; i++) {
        res = mulLow(res, i);
    }
    for (int i = (int)(res.size()) - 1; i >= 0; i--) {
        cout << res.at(i);
    }
    cout << endl;
    return 0;
}

例题4：高精度乘方（快速幂）

题目描述

计算 a 的 b 次方，其中 a 是一个不超过 1000 位的整数，b 是一个不超过 10⁴ 的整数。

输入：第一行一个大整数 a，第二行整数 b。 输出：a^b 的精确值。

思路解析

• 使用快速幂算法，将指数 b 二进制分解。
• 高精度乘法（大数 × 大数）用于中间结果累积。
• 注意：b=0 时结果为 1。

代码实现

#include <bits/stdc++.h>
using namespace std;

vector<int> mulHigh(vector<int> &a, vector<int> &b) {
    vector<int> res(a.size() + b.size(), 0);
    for (int i = 0; i < (int)(a.size()); i++) {
        for (int j = 0; j < (int)(b.size()); j++) {
            res.at(i + j) += a.at(i) * b.at(j);
        }
    }
    int carry = 0;
    for (int i = 0; i < (int)(res.size()); i++) {
        int val = res.at(i) + carry;
        res.at(i) = val % 10;
        carry = val / 10;
    }
    while ((int)(res.size()) > 1 && res.back() == 0) res.pop_back();
    return res;
}

vector<int> powHigh(vector<int> &base, int exp) {
    vector<int> res = {1};
    vector<int> cur = base;
    while (exp > 0) {
        if (exp & 1) {
            res = mulHigh(res, cur);
        }
        cur = mulHigh(cur, cur);
        exp >>= 1;
    }
    return res;
}

int main() {
    string s;
    int exp;
    cin >> s >> exp;
    vector<int> a;
    for (int i = (int)(s.size()) - 1; i >= 0; i--) {
        a.push_back(s.at(i) - '0');
    }
    vector<int> res = powHigh(a, exp);
    for (int i = (int)(res.size()) - 1; i >= 0; i--) {
        cout << res.at(i);
    }
    cout << endl;
    return 0;
}

例题5：高精度除以低精度

题目描述

输入一个大整数 a（不超过 1000 位）和一个低精度整数 b（1 ≤ b ≤ 10⁹），输出 a ÷ b 的商和余数。

输入：第一行大整数 a，第二行整数 b。 输出：两行，第一行商，第二行余数。

思路解析

• 从高位向低位逐位处理，用 remainder 记录当前余数。
• 每次将余数 ×10 + 当前位，然后除以 b 得到商的一位，余数更新。
• 去除商的前导零。

代码实现

#include <bits/stdc++.h>
using namespace std;

vector<int> divLow(vector<int> &a, int b, int &rem) {
    vector<int> res;
    long long remainder = 0;
    for (int i = (int)(a.size()) - 1; i >= 0; i--) {
        remainder = remainder * 10 + a.at(i);
        res.push_back(remainder / b);
        remainder %= b;
    }
    rem = remainder;
    reverse(res.begin(), res.end());
    while ((int)(res.size()) > 1 && res.back() == 0) res.pop_back();
    return res;
}

int main() {
    string s;
    int b;
    cin >> s >> b;
    vector<int> a;
    for (int i = (int)(s.size()) - 1; i >= 0; i--) {
        a.push_back(s.at(i) - '0');
    }
    int rem;
    vector<int> res = divLow(a, b, rem);
    for (int i = (int)(res.size()) - 1; i >= 0; i--) {
        cout << res.at(i);
    }
    cout << endl << rem << endl;
    return 0;
}

例题6：高精度除以高精度

题目描述

输入两个大整数 a 和 b（b ≠ 0），输出 a ÷ b 的商和余数。

输入：两行，每行一个大整数。 输出：两行，第一行商，第二行余数。

思路解析

• 若 a < b，商为 0，余数为 a。
• 否则，模拟竖式除法。计算位数差 shift，将除数扩大 10^shift 倍。
• 逐位试商：当前余数不断减去扩大后的除数，直到小于除数，减的次数即为商的一位。
• 然后除数右移一位，重复直到所有位处理完毕。
• 去除商的前导零。

代码实现

#include <bits/stdc++.h>
using namespace std;

bool greaterOrEqual(vector<int> &a, vector<int> &b) {
    if (a.size() != b.size()) return a.size() > b.size();
    for (int i = (int)(a.size()) - 1; i >= 0; i--) {
        if (a.at(i) != b.at(i)) return a.at(i) > b.at(i);
    }
    return true;
}

vector<int> sub(vector<int> &a, vector<int> &b) {
    vector<int> res;
    int borrow = 0;
    for (int i = 0; i < (int)(a.size()); i++) {
        int diff = a.at(i) - borrow;
        if (i < (int)(b.size())) diff -= b.at(i);
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        res.push_back(diff);
    }
    while ((int)(res.size()) > 1 && res.back() == 0) res.pop_back();
    return res;
}

vector<int> divHigh(vector<int> &a, vector<int> &b, vector<int> &rem) {
    vector<int> res;
    rem = a;
    if (!greaterOrEqual(a, b)) {
        res.push_back(0);
        return res;
    }
    int shift = (int)(a.size()) - (int)(b.size());
    vector<int> divisor = b;
    reverse(divisor.begin(), divisor.end());
    for (int i = 0; i < shift; i++) divisor.push_back(0);
    reverse(divisor.begin(), divisor.end());
    for (int i = shift; i >= 0; i--) {
        int cnt = 0;
        while (greaterOrEqual(rem, divisor)) {
            rem = sub(rem, divisor);
            cnt++;
        }
        res.push_back(cnt);
        if (i > 0) {
            divisor.erase(divisor.begin());
            while ((int)(divisor.size()) > 1 && divisor.back() == 0) divisor.pop_back();
        }
    }
    reverse(res.begin(), res.end());
    while ((int)(res.size()) > 1 && res.back() == 0) res.pop_back();
    return res;
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    vector<int> a, b;
    for (int i = (int)(s1.size()) - 1; i >= 0; i--) {
        a.push_back(s1.at(i) - '0');
    }
    for (int i = (int)(s2.size()) - 1; i >= 0; i--) {
        b.push_back(s2.at(i) - '0');
    }
    vector<int> rem;
    vector<int> res = divHigh(a, b, rem);
    for (int i = (int)(res.size()) - 1; i >= 0; i--) {
        cout << res.at(i);
    }
    cout << endl;
    for (int i = (int)(rem.size()) - 1; i >= 0; i--) {
        cout << rem.at(i);
    }
    cout << endl;
    return 0;
}

---

六、课后练习（20题，含可直接点击的链接）

力扣（LeetCode）

序号	题目名称	题号	链接
1	字符串相加	415	https://leetcode.cn/problems/add-strings/
2	字符串相乘	43	https://leetcode.cn/problems/multiply-strings/
3	超级次方	372	https://leetcode.cn/problems/super-pow/

信息学奥赛一本通（ybt.ssoier.cn）

序号	题目名称	题号	链接
4	大整数加法	1168	https://ybt.ssoier.cn/problem_show.php?pid=1168
5	大整数减法	1169	https://ybt.ssoier.cn/problem_show.php?pid=1169
6	大整数乘法	1170	https://ybt.ssoier.cn/problem_show.php?pid=1170
7	大整数除法	1171	https://ybt.ssoier.cn/problem_show.php?pid=1171
8	求10000以内n的阶乘	1172	https://ybt.ssoier.cn/problem_show.php?pid=1172

洛谷（Luogu）

序号	题目名称	题号	链接
9	A+B Problem（高精）	P1601	https://www.luogu.com.cn/problem/P1601
10	A*B Problem（高精）	P1303	https://www.luogu.com.cn/problem/P1303
11	阶乘之和	P1009	https://www.luogu.com.cn/problem/P1009
12	2的幂次方	P1010	https://www.luogu.com.cn/problem/P1010
13	高精度开根	P2291	https://www.luogu.com.cn/problem/P2291

Codeforces

序号	题目名称	题号	链接
14	1702A - Round Down the Price	1702A	https://codeforces.com/problemset/problem/1702/A
15	1650A - Array Balancing	1650A	https://codeforces.com/problemset/problem/1650/A

AtCoder

序号	题目名称	题号	链接
16	ABC 126 B - YYMM or MMYY	ABC126B	https://atcoder.jp/contests/abc126/tasks/abc126_b
17	ABC 154 C - Distinct or Not	ABC154C	https://atcoder.jp/contests/abc154/tasks/abc154_c

AcWing

序号	题目名称	题号	链接
18	高精度加法	791	https://www.acwing.com/problem/content/793/
19	高精度乘法	793	https://www.acwing.com/problem/content/795/
20	高精度除法	794	https://www.acwing.com/problem/content/796/

---

七、注意事项

1. 存储方向：务必保持低位在前（下标0是个位），这样进位时只需在末尾添加。
2. 前导零处理：减法、除法、乘法后可能出现 0123 形式，要去除高位的零，但保留一个零。
3. 负数处理：本讲义只涉及非负整数。若有负数，需先判断符号，转换为绝对值运算。
4. 性能考虑：高精度乘法 O(n×m)，当位数很大时（如 10⁵ 位）需用 FFT 优化，但竞赛一般不会。
5. 输入输出：使用 string 接收，避免 cin 直接读入 int 溢出。
6. 临时变量类型：中间乘积可能很大，用 long long 暂存进位。
7. 比较函数：减法、除法前需确保 a ≥ b，否则需交换并输出负号。
8. 除数为0：高精度除法中，除数不能为0，需特判。
9. 乘方指数为0：结果为1。
10. 高精度除以高精度：试商过程效率较低，可优化为二分试商，但竞赛中通常数据量不大。

---

八、课堂总结

核心要点	说明
高精度算法定义	用数组/字符串存储每一位，模拟竖式运算。
存储方式	vector<int> 低位在前，高位在后。
加法	逐位相加 + 进位。
减法	逐位相减 + 借位，注意去除前导零。
乘法（大×小）	逐位乘 + 进位。
乘法（大×大）	双重循环累加，最后统一进位。
除法（大÷小）	从高位到低位逐位求商，余数传递。
除法（大÷大）	模拟竖式，试商后相减。
乘方	快速幂 + 高精度乘法。
典型应用	大整数加减乘除、阶乘、乘方、高精度开方等。
时间复杂度	加法 O(n)，减法 O(n)，乘法 O(n×m)，除法 O(n×m)。

教练寄语：高精度算法是信息学竞赛中处理大数据的基础工具。请务必亲手实现一遍加法、减法、乘法、除法（低精度和高精度）、乘方，并完成课后练习。当你能够熟练编写高精度运算时，你将不再受整数范围的限制，可以自由处理天文数字。

---

参考资料

• 【书籍】《信息学奥赛一本通》第3章：高精度计算
• 【在线资源】OI Wiki - 高精度
• 【在线资源】洛谷 - 高精度题单