基础算法题型——高精度
数据的值特别大时，各种类型都存不下时，此时我们就要用高精度算法来模拟加减乘除。
模板：
先用字符串读入这个数，再用数组逆序存储该数的每一位；
用数组模拟列竖式加减乘除的过程。
一.高精度加法
题目来源：洛谷
题目链接：P1601 高精度加法
题目描述
解法
1.用字符串读入数据；
2.将字符串的每一位拆分，逆序放在数组中；
存放技巧：每一位要存放的数在数组的下标与在字符串的下标之和等于字符串长度，同时要注意下标从零开始，即 a[n - i - 1] = x[i]
注意点：数字字符存放数据到整形数组时需要减去‘0’
3.模拟列竖式加法过程
（1）将对应位求和，加上上一位进位；
（2）处理余数（x % 10）
（3）处理进位 (x / 10)
重复上述步骤
4.处理结果位数
实现代码
#include <iostream> using namespace std; const int N = 1e6 + 10; string x, y; int a[N], b[N], c[N]; int la, lb, lc; void add(int c[], int a[], int b[]) { for(int i = 0; i < lc; i++) { c[i] += a[i] + b[i]; // 每一位相加，同时加上进位 c[i + 1] = c[i] / 10; // 处理进位 c[i] = c[i] % 10; // 处理余数 } if(c[lc]) lc++; } int main() { cin >> x >> y; // 拆分每一位，逆序放在数组中 la = x.size(); lb = y.size(); lc = max(la, lb); for(int i = 0; i < la; i++) a[la - i - 1] = x[i] - '0'; for(int i = 0; i < lb; i++) b[lb - i - 1] = y[i] - '0'; // 模拟 c = a + b 过程 add(c, a, b); // 输出结果 for(int i = lc - 1; i >= 0; i--) cout << c[i]; return 0; }二.高精度减法
题目来源：洛谷
题目链接：P2142 高精度减法
题目描述
解法
1.先用字符串读入数据；
2.判断两个数的大小，让较大的数在前。注意字典序VS数的大小：
（1）位数相等：按字典序比较
（2）位数不等：按长度比较
3.将字符串每一位拆分逆序存放在数组中；
4.模拟列竖式减法过程：
（1）对应位相减，加上原位（可能被上一位借位）；
（2）如果结果小于0，处理借位（ x[i + 1]-- ），处理余数（ x[i] += 10 ）
重复上述步骤
5.处理前导零和输出位数，但长度不小于1（最小值为0长度为1），方便输出
实现代码
#include <iostream> using namespace std; const int N = 1e6 + 10; string x, y; int a[N], b[N], c[N]; int la, lb, lc; bool cmp(string& x, string& y) { if(x.size() == y.size()) return x < y; return x.size() < y.size(); } void sub(int c[], int a[], int b[]) { for(int i = 0; i < lc; i++) { c[i] += a[i] - b[i]; // 对应位相减 if(c[i] < 0) // 处理进位和余数 { c[i + 1]--; c[i] += 10; } } // 处理前导0 while(lc > 1 && c[lc - 1] == 0) lc--; } int main() { cin >> x >> y; // 比较大小 if(cmp(x, y)) { swap(x, y); cout << '-'; } // 逆序存放每一位 la = x.size(); lb = y.size(); lc = la; for(int i = 0; i < la; i++) a[la - i - 1] = x[i] - '0'; for(int i = 0; i < lb; i++) b[lb - i - 1] = y[i] - '0'; // 模拟 c = a - b; sub(c, a, b); for(int i = lc - 1; i >= 0; i--) cout << c[i]; return 0; }三.高精度乘法
题目来源：洛谷
题目链接：P1303 A*B Problem
题目描述
解法
采用无进位相乘再相加的方法：
a.还是列竖式计算，但是每一位相乘的时候不考虑进位，直接把结果放到对应位上。
b.等到所有对应位置乘完且累加完完后，统一处理进位。
c.存放数组c对应位下标等于a对应位下标与b对应位下标之和。
1.用字符串输入数据；
2.将字符串每一位拆分逆序存放在数组中；
3.模拟无进位相乘再相加的过程
（1）对应位乘积
（2）逐个处理进位，取余数
4.处理前导0和输出位数。
实现代码
#include <iostream> using namespace std; const int N = 1e6 + 10; string x, y; int a[N], b[N], c[N]; int la, lb, lc; void mul(int c[], int a[], int b[]) { // 无进位相乘 for(int i = 0; i < la; i++) { for(int j = 0; j < lb; j++) c[i + j] += a[i] * b[j]; } // 逐个处理进位 for(int i = 0; i < lc; i++) { c[i + 1] += c[i] / 10; c[i] %= 10; } // 处理前导0 while(lc > 1 && c[lc - 1] == 0) lc--; } int main() { cin >> x >> y; // 逆序存放 la = x.size(); lb = y.size(); lc = la + lb; for(int i = 0; i < la; i++) a[la - i - 1] = x[i] - '0'; for(int i = 0; i < lb; i++) b[lb - i - 1] = y[i] - '0'; // 模拟 c = a * b mul(c, a, b); // 输出结果 for(int i = lc - 1; i >= 0; i--) cout << c[i]; return 0; }四.高精度乘法
题目来源：洛谷
题目链接：P1480 A/B Problem（高精度除法Ⅰ）
题目描述
解法
这道题其实是高精度 ➗ 低精度
1.将第一个数以字符串输入，并把每一位拆分逆序存在数组中；
2.模拟列竖式除法过程
从高位开始遍历被除数，用t标记被除数，除数是b；
（1）更新被除数 t = t * 10 + a[i];
（2）处理商（t / b）
（3）处理余数（t % b），用t保存余数
重复上述步骤
3.处理前导0和输出位数
实现代码
#include <iostream> using namespace std; const int N = 1e6 + 10; typedef long long LL; string x; int a[N], b, c[N]; int la, lc; void div(int c[], int a[], int b) { LL t = 0; // 标记每次除完后的余数 for(int i = la - 1; i >= 0; i--) { // 计算当前的被除数 t = t * 10 + a[i]; c[i] = t / b; t = t % b; } // 处理前导0 while(lc > 1 && c[lc - 1] == 0 ) lc--; } int main() { cin >> x >> b; la = x.size(); lc = la; for(int i = 0; i < la; i++) a[la - i - 1] = x[i] - '0'; // 模拟 c = a / b div(c, a, b); // 输出结果 for(int i = lc - 1; i >= 0; i--) cout << c[i]; return 0; }