零、前言
高精度运算是某些题目涉及大数值运算且范围超出语言内置类型允许范围时采取的处理手段，原理就是小学列竖式计算的代码化，比较易懂，本文介绍高精度加法、减法、乘法、除法、以及高精度快速幂，附模板即OJ链接练手。
一、加法
高精度加法步骤
-
倒序存储加数，低位放数组前面，高位放数组后面(类似小端存储)
-
从
低位到高位
，累加，进位，求余
-
答案数组从末尾到开头即为高位——低位
P1601 A+B
P1601 A+B Problem（高精） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define IOTIE ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
const int N = 505;
int A[N]{0}, B[N]{0}, C[N]{0};
int la, lb, lc;
void add()
{
//累加、进位、取余
for (int i = 0; i < lc; i++)
C[i] += A[i] + B[i], C[i + 1] += C[i] / 10, C[i] %= 10;
if (C[lc]) //末位进位，位长+1
lc++;
}
int main()
{
IOTIE
// freopen("in.txt", "r", stdin);
string a, b;
cin >> a >> b, la = a.size(), lb = b.size(), lc = max(la, lb);
for (int i = 0; i < la; i++)
A[la - i - 1] = (a[i] ^ 48);
for (int i = 0; i < lb; i++)
B[lb - i - 1] = (b[i] ^ 48);
add();
for (int i = lc - 1; i >= 0; i--)
cout << C[i];
return 0;
}
二、减法
高精度减法步骤
-
倒序存储加数，低位放数组前面，高位放数组后面(类似小端存储)
-
被减数A，减数B，如果A < B，交换A，B，输出负号
-
从
低位到高位
，逐位求差，借位，存差
-
答案数组从末尾到开头即为高位——低位
P2142 高精度减法
P2142 高精度减法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define IOTIE ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
const int N = 10100;
int A[N]{0}, B[N]{0}, C[N]{0};
int la, lb, lc;
bool cmp()
{
if (la != lb)
return la > lb;
for (int i = la - 1; i >= 0; i--)
if (A[i] != B[i])
return A[i] > B[i];
return true;
}
void sub()
{
for (int i = 0; i < lc; i++)
{
if (A[i] < B[i])//借位
A[i] += 10, A[i + 1]--;
C[i] = A[i] - B[i];
}
while (lc && !C[lc]) //前导0
lc--;
}
int main()
{
IOTIE
// freopen("in.txt", "r", stdin);
string a, b;
cin >> a >> b, la = a.size(), lb = b.size(), lc = max(la, lb);
for (int i = 0; i < la; i++)
A[la - i - 1] = (a[i] ^ 48);
for (int i = 0; i < lb; i++)
B[lb - i - 1] = (b[i] ^ 48);
if (!cmp())
swap(A, B), cout << '-';
sub();
for (int i = lc; i >= 0; i--)
cout << C[i];
return 0;
}
三、乘法
高精度乘法步骤
-
倒序存储加数，低位放数组前面，高位放数组后面(类似小端存储)
-
从
低位到高位
，累加乘积，进位，求余
-
答案数组从末尾到开头即为高位——低位
P1303 A*B
P1303 A*B Problem - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define IOTIE ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
const int N = 4010;
int A[N]{0}, B[N]{0}, C[N]{0};
int la, lb, lc;
void mul()
{
for (int i = 0; i < la; i++)
for (int j = 0; j < lb; j++)
C[i + j] += A[i] * B[j], C[i + j + 1] += C[i + j] / 10, C[i + j] %= 10;
while (lc && !C[lc])//前导0
lc--;
}
int main()
{
IOTIE
// freopen("in.txt", "r", stdin);
string a, b;
cin >> a >> b, la = a.size(), lb = b.size(), lc = la + lb;
for (int i = 0; i < la; i++)
A[la - i - 1] = (a[i] ^ 48);
for (int i = 0; i < lb; i++)
B[lb - i - 1] = (b[i] ^ 48);
mul();
for (int i = lc; i >= 0; i--)
cout << C[i];
return 0;
}
四、除法
高精度除法步骤
-
倒序存储加数，低位放数组前面，高位放数组后面(类似小端存储)
-
从
高位到低位
，当前被除数，存商，求余数
-
答案数组从末尾到开头即为高位——低位
P1480 A/B
P1480 A/B Problem - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define IOTIE ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
const int N = 10100;
int A[N]{0}, b, C[N]{0};
int la, lc;
void div()
{
ll num = 0;
for (int i = la - 1; i >= 0; i--)
num = (num << 3) + (num << 1) + A[i], C[i] = num / b, num %= b;
while (lc && !C[lc])
lc--;
}
int main()
{
IOTIE
// freopen("in.txt", "r", stdin);
string a;
cin >> a >> b, la = a.size(), lc = la;
for (int i = 0; i < la; i++)
A[la - i - 1] = (a[i] ^ 48);
div();
for (int i = lc; i >= 0; i--)
cout << C[i];
return 0;
}
五、高精度快速幂
关于二分快速幂：
二分快速幂和快读快写模板【C++】-CSDN博客
其实就是把普通二分快速幂中结果和底数相乘亦即底数自乘的部分换成高精度乘法即可，这里不给出代码只需要替换普通二分快速幂中的乘法为高精度乘法即可，我们直接看一道例题来练手。
麦森数
[P1045
NOIP2003 普及组] 麦森数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
其实就是一个高精度快速幂裸题，由于题目只要求我们最后输出后500位，所以我们高精度乘法的时候只需要进行后500位的计算即可
那么位数如何求呢？
显然存在k ，10^k <= 2^p - 1 < 10^(k + 1)
显然2^p - 1 的位数就是k + 1，而2^p - 1和 2^p的十进制位数相同，那么有
10^k = [2 ^ p]，k = p * log10 (2)
我们的位数就是 p * log10 (2) + 1，log10可以用库函数
代码如下：
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define IOTIE ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define sc scanf
#define int long long
const int N = 500;
typedef vector<int> VI;
int p;
VI ans(N + 1), a(N + 1);
VI mul(VI &x, VI &y)
{
VI ret(N + 1);
for (int i = 0; i < N; i++)
for (int j = 0; j + i < N; j++)
ret[i + j] += x[i] * y[j], ret[i + j + 1] += ret[i + j] / 10, ret[i + j] %= 10;
return ret;
}
void quickpower()
{
ans[0] = 1, a[0] = 2;
while (p)
{
if (p & 1)
ans = mul(ans, a);
a = mul(a, a), p >>= 1;
}
ans[0]--;
}
signed main()
{
IOTIE
// freopen("in.txt", "r", stdin);
cin >> p;
cout << floor(p * log10(2) + 1) << '\n';
quickpower();
for (int i = 499; i >= 0; i--)
{
cout << ans[i];
if ((500 - i) % 50 == 0)
cout << '\n';
}
return 0;
}
