C++ 算法技巧 — 模拟与高精度 (Simulation & High Precision)

章节概述

模拟是按题意逐步执行操作；高精度用于处理超出标准整数范围的大数运算。
两者是算法竞赛中最基础的实现能力。

核心原理

1. 高精度存储方式

将数字按位存入数组，低位在下标 0（逆序存储），方便进位处理。

数字: 12345
数组: [5, 4, 3, 2, 1]   (低位在低地址)

2. 高精度加法核心

for i in 0..len-1:
    sum[i] += a[i] + b[i]
    sum[i+1] += sum[i] / 10   // 进位
    sum[i] %= 10               // 当前位

3. 高精度乘法核心

res[i+j] += a[i] * b[j]        // 10^i × 10^j = 10^(i+j)
然后逐位处理进位

4. 前导零处理

while (len > 1 && res[len-1] == 0) len--;

关键数据结构

• A_容器_Container — vector 可替代固定数组

---

P1601 A+B Problem（高精）

题目: 高精度加法，两个不超过 10^500 位的非负整数之和。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main() {
    string a, b;
    cin >> a >> b;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    int len = max(a.size(), b.size());
    int sum[505] = {0};
    for (int i = 0; i < len; i++) {
        if (i < (int)a.size()) sum[i] += a[i] - '0';
        if (i < (int)b.size()) sum[i] += b[i] - '0';
    }
    for (int i = 0; i < len; i++) {
        if (sum[i] >= 10) {
            sum[i + 1] += sum[i] / 10;
            sum[i] %= 10;
        }
    }
    if (sum[len] > 0) len++;
    for (int i = len - 1; i >= 0; i--)
        cout << sum[i];
    cout << endl;
    return 0;
}

---

P1303 A*B Problem（高精）

题目: 高精度乘法，两个不超过 2000 位的非负整数之积。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main() {
    string a, b;
    cin >> a >> b;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    int res[4005] = {0};
    for (int i = 0; i < (int)a.size(); i++)
        for (int j = 0; j < (int)b.size(); j++)
            res[i + j] += (a[i] - '0') * (b[j] - '0');
    int len = a.size() + b.size();
    for (int i = 0; i < len; i++) {
        res[i + 1] += res[i] / 10;
        res[i] %= 10;
    }
    while (len > 1 && res[len - 1] == 0) len--;
    for (int i = len - 1; i >= 0; i--)
        cout << res[i];
    cout << endl;
    return 0;
}

---

P1009 [NOIP1998 普及组] 阶乘之和

题目: S = 1! + 2! + … + n! (n ≤ 50)，用高精度计算。

#include <iostream>
using namespace std;
 
int res[100] = {0}, fac[100] = {1};
 
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 100; j++)
            fac[j] *= i;
        for (int j = 0; j < 99; j++) {
            fac[j + 1] += fac[j] / 10;
            fac[j] %= 10;
        }
        for (int j = 0; j < 100; j++) {
            res[j] += fac[j];
            res[j + 1] += res[j] / 10;
            res[j] %= 10;
        }
    }
    int p = 99;
    while (p > 0 && res[p] == 0) p--;
    for (; p >= 0; p--) cout << res[p];
    cout << endl;
    return 0;
}

推荐练习题（洛谷）

• P1601 A+B Problem(高精)
• P1303 A*B Problem

---

相关技巧

---

• 数组: 高精度数用数组按位存储
• 循环: 逐位运算依赖循环
• 函数结构体: 封装高精度运算为结构体+运算符重载

多平台练习

| 洛谷 | 本题单 | 竞赛基础 |
| POJ (北大) | PKU JudgeOnline | 经典题目，适合巩固 |
| HDU (杭电) | HDU OJ | 暑期多校训练 |
| Codeforces | Codeforces | 国际竞赛，适合提升 |