高精度专项训练练习题
题单介绍
高精度算法（High Accuracy Algorithm）是处理大数字的数学计算方法。在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除，乘方，阶乘，开方等运算。对于非常庞大的数字无法在计算机中正常存储，于是，将这个数字拆开，拆成一位一位的，或者是四位四位的存储到一个数组中， 用一个数组去表示一个数字，这样这个数字就被称为是高精度数。高精度算法就是能处理高精度数各种运算的算法，但又因其特殊性，故从普通数的算法中分离，自成一家。这里列举出一些涉及高精度的题目：
知识点1 高精度比较大小：
- [高精度大小比较](https://www.luogu.com.cn/problem/U372548)
- [高精度的排序](https://www.luogu.com.cn/problem/P1781)
知识点2 高精度四则运算：
1. [高精度加高精度](https://www.luogu.com.cn/problem/P1601)
2. [高精度减高精度](https://www.luogu.com.cn/problem/P2142)
3. [高精度乘低精度](https://www.luogu.com.cn/problem/U371642)
4. [高精度乘高精度](https://www.luogu.com.cn/problem/P1303)
5. [高精度除以单精度](https://www.luogu.com.cn/problem/P1480)
6. [高精度对单精度取模](https://www.luogu.com.cn/problem/U371927)
知识点3 高精度综合运用：
- [阶乘之和](https://www.luogu.com.cn/problem/P1009)
- [阶乘数码](https://www.luogu.com.cn/problem/P1591)
- [产生数](https://www.luogu.com.cn/problem/P1037)
- [Hanoi双塔问题](https://www.luogu.com.cn/problem/P1096)
- [矩阵取数游戏](https://www.luogu.com.cn/problem/P1005)
高精度拔高训练题目：
- [高精度除以高精度](https://www.luogu.com.cn/problem/P5432)
- [高精度大综合](https://www.luogu.com.cn/problem/P1932)
最后附上高精度模板（一个结构体）：
```cpp
# include <cstdio>
# include <iostream>
# include <cstring>
# include <algorithm>
# include <cmath>
using namespace std;
# define FOR(i, a, b) for(int i = a; i <= b; i++)
# define _FOR(i, a, b) for(int i = a; i >= b; i--)
struct BigInt
{
static const int M = 1000;
int num[M + 10], len;
BigInt() { clean(); }
void clean(){
memset(num, 0, sizeof(num));
len = 1;
}
void read(){
char str[M + 10];
scanf("%s", str);
len = strlen(str);
FOR(i, 1, len)
num[i] = str[len - i] - '0';
}
void write(){
_FOR(i, len, 1)
printf("%d", num[i]);
puts("");
}
void itoBig(int x){
clean();
while(x != 0){
num[len++] = x % 10;
x /= 10;
}
if(len != 1) len--;
}
bool operator < (const BigInt &cmp) const {
if(len != cmp.len) return len < cmp.len;
_FOR(i, len, 1)
if(num[i] != cmp.num[i]) return num[i] < cmp.num[i];
return false;
}
bool operator > (const BigInt &cmp) const { return cmp < *this; }
bool operator <= (const BigInt &cmp) const { return !(cmp < *this); }
bool operator != (const BigInt &cmp) const { return cmp < *this || *this < cmp; }
bool operator == (const BigInt &cmp) const { return !(cmp < *this || *this < cmp); }
BigInt operator + (const BigInt &A) const {
BigInt S;
S.len = max(len, A.len);
FOR(i, 1, S.len){
S.num[i] += num[i] + A.num[i];
if(S.num[i] >= 10){
S.num[i] -= 10;
S.num[i + 1]++;
}
}
while(S.num[S.len + 1]) S.len++;
return S;
}
BigInt operator - (const BigInt &A) const {
BigInt S;
S.len = max(len, A.len);
FOR(i, 1, S.len){
S.num[i] += num[i] - A.num[i];
if(S.num[i] < 0){
S.num[i] += 10;
S.num[i + 1]--;
}
}
while(!S.num[S.len] && S.len > 1) S.len--;
return S;
}
BigInt operator * (const BigInt &A) const {
BigInt S;
if((A.len == 1 && A.num[1] == 0) || (len == 1 && num[1] == 0)) return S;
S.len = A.len + len - 1;
FOR(i, 1, len)
FOR(j, 1, A.len){
S.num[i + j - 1] += num[i] * A.num[j];
S.num[i + j] += S.num[i + j - 1] / 10;
S.num[i + j - 1] %= 10;
}
while(S.num[S.len + 1]) S.len++;
return S;
}
BigInt operator / (const BigInt &A) const {
BigInt S;
if((A.len == 1 && A.num[1] == 0) || (len == 1 && num[1] == 0)) return S;
BigInt R, N;
S.len = 0;
_FOR(i, len, 1){
N.itoBig(10);
R = R * N;
N.itoBig(num[i]);
R = R + N;
int flag = -1;
FOR(j, 1, 10){
N.itoBig(j);
if(N * A > R){
flag = j - 1;
break;
}
}
S.num[++S.len] = flag;
N.itoBig(flag);
R = R - N * A;
}
FOR(i, 1, S.len / 2) swap(S.num[i], S.num[len - i + 1]);
while(!S.num[S.len] && S.len > 1) S.len--;
return S;
}
BigInt operator % (const BigInt &A) const {
BigInt S;
BigInt P = *this / A;
S = *this - P * A;
return S;
}
};
``````