2026/4/28

高精度（High Precision），本质就是：计算机原生类型存不下的超大整数/小数，用数组/字符串模拟手工竖式计算。

一、为什么需要高精度？
常见整数类型范围：

int：约 ±21亿
long long：约 ±9e18
一旦题目出现：

100位、1000位、10000位大数
阶乘、斐波那契、组合数爆 long long
就必须用高精度。
二、核心思想
用数组存数字
一般低位在前（方便进位）
例如：1234 存为 [4,3,2,1]

模拟小学竖式

加法：同位相加 + 进位
减法：同位相减 + 借位
乘法：逐位相乘 + 进位
除法：逐位试商 + 余数
处理前导零/符号
计算完要去掉多余的 0，负数单独处理。

三、高精度整数加法（最基础）
步骤
字符串逆序存入数组（低位在前）
逐位相加，处理进位
去掉前导零，逆序输出
示例代码思路（C++风格）
vector add(vector &a, vector &b) {
vector c;
int t = 0;
for (int i = 0; i < a.size() || i < b.size() || t; i++) {
if (i < a.size()) t += a[i];
if (i < b.size()) t += b[i];
c.push_back(t % 10);
t /= 10;
}
return c;
}
四、高精度减法
要点
先比较大小，保证 大 − 小
逐位相减，不够减借位
去掉前导零
bool cmp(vector &a, vector &b) {
if (a.size() != b.size()) return a.size() > b.size();
for (int i = a.size()-1; i >= 0; i--)
if (a[i] != b[i]) return a[i] > b[i];
return true;
}

vector sub(vector &a, vector &b) {
vector 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);
t = t < 0 ? 1 : 0;
}
while (c.size() > 1 && c.back() == 0) c.pop_back();
return c;
}
五、高精度 × 低精度（大数 × 普通 int）
vector mul(vector &a, int b) {
vector c;
long long t = 0;
for (int i = 0; i < a.size() || t; i++) {
if (i < a.size()) t += (long long)a[i] * b;
c.push_back(t % 10);
t /= 10;
}
while (c.size() > 1 && c.back() == 0) c.pop_back();
return c;
}
六、高精度 × 高精度（最难但常考）
公式：c[i+j] += a[i] * b[j]，最后统一处理进位。

vector mul(vector &a, vector &b) {
vector 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 k = 0; k < c.size() || t; k++) {t += c[k];if (k < c.size()) c[k] = t % 10;else c.push_back(t % 10);t /= 10;
}
while (c.size() > 1 && c.back() == 0) c.pop_back();
return c;

}
七、高精度 ÷ 低精度
vector div(vector &a, int b, int &r) {
vector 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;
}
八、通用输入输出模板
// 字符串转数组（低位在前）
vector to_vec(string s) {
vector a;
for (int i = s.size()-1; i >= 0; i--)
a.push_back(s[i] - '0');
return a;
}

// 数组输出
void print(vector &a) {
for (int i = a.size()-1; i >= 0; i--)
cout << a[i];
cout << endl;
}