OI退役笔记-005：高精度总结

前言

高精度是 C++ 竞赛的基本算法，适用于处理大数之间的加减乘除基本运算（因为 C++ 的变量无法容纳过多位的数字） 而高精度即用数组模拟运算的算法就非常重要。

高精度处理思路

相同位相加减乘除，再处理进位 进位处理： （1）加法：

... c[i] = a[i] + b[i]; if (c[i] > 9){ c[i] -= 10; ++c[i + 1]; } ...

（1）减法：

... c[i] = a[i] - b[i]; if (c[i] < 0){ c[i] += 10; --c[i + 1]; } // 注意，应先判断大小，用大数减小数，再处理正负 ...

（1）乘法：

... c[i] = a[i] * b[i]; if (c[i] > 9){ int t = c[i] / 10; c[i + 1] += t; c[i] %= 10; } ...

（1）除法：

// 取余或算小数部分应视情况而定（好敷衍）

高精度数的读入

需加语句、头文件：

#include <iostream> using namespace std; // 用字符储存高精度方便运算 // 因为，无论何种运算，最大值为 9 * 9 = 81 // char 型刚好容下，且 char 数组可以用 strlen 获取长度。 char a[10010];

读入：

void read() { string s; cin >> s; int len = s.length(); for (int i = 1; i <= n; ++i) { a[len - i] - '0'; } }

加法算法

char a[10010], b[10010], c[10010]; void hp_add() { int i = 1; while (i <= strlen(a) || i <= strlen(b)) { c[i] = a[i] + b[i]; if (c[i] > 9) { c[i] -= 10; ++c[i + 1]; ++i; } } }

减法算法

char a[10010], b[10010], c[10010]; void hp_sub() { int i = 1; while (i <= strlen(a) || i <= strlen(b)) { c[i] = a[i] - b[i]; if (c[i] < 0) { c[i] += 10; --c[i + 1]; ++i; } } }

乘法算法

char a[10010], b[10010], c[10010]; void hp_mul() { int i = 1; for(int i = 1; i <= strlen(a); ++i) { for (int j = 1; j<= strlen(b); ++j){ c[i + j - 1] += a[i] * b[j]; if (c[i + j - 1] > 9) { c[i + j] += c[i + j - 1] / 9; c[i + j - 1] %= 9; } } } } // 注意，最后的 len 应该为 lena + lenb

除法算法

高精度除以单精度：

int b; // long、 long long 等都可以 char a[10010], c[10010]; void hp_div(){ // x 用于存上一步的余数 int x = 0; for (int i = 1; i <= strlen(a); ++i) { c[i] = (x * 10 + a[i]) / b; x = (x * 10 + a[i]) % b; } // 最后余数可能有剩余，可以适当修改函数返回或继续向下除，算取小数点后位数 }

高精度除以单精度： 懒得写 不会

作者：Rotch 日期：2020-10-05 修改：2020-10-05