高精度
今天我们就说一件事：高精度。
高精度是什么玩意儿？
什么是高精度高精度算法？高精度算法属于处理大数字的数学计算方法。在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除。
好家伙，合着今天讲数学？
没错，我们今天直接梦回一年级，思考底层的加减乘除、四则运算。
数据类型的极大值、极小值
首先，在讲高精度以前，我们先来认识一下比较常见的几种类型的最大值、最小值。
最大值：
int类型：2147483647
char类型：127
short类型：32767
long类型：2147483647
long long类型：9223372036854775807
signed char类型：127
unsigned char类型：255
unsigned short类型：65535
unsigned int类型：4294967295
unsigned long类型：4294967295
unsigned long long类型：18446744073709551615
最小值：
char类型：-128
short类型：-32768
int类型：-2147483648
long类型：-2147483648
long long类型：-9223372036854775808
unsigned char类型：-128
大家没必要记，看看就OK了，有个大概的概念就行。
加法
加法这个事儿，大家肯定都很熟悉吧？
不是，我是说也许。
现在，我们来看看如何加。
很多人最开始一见到这个题，很高兴啊，“太简单了！我直接用long long”，然后就悲剧了。
我们想啊，题中给了一个条件：
那它肯定、肯定是不能使用常规的手法储存的，它的最大长度（501位)为远远超过 long long 类型的最大值。
我们要使用一些奇怪的东西，来储存它，比如说——字符串。
前面我们有说过，string类型没有长度限制，那我们可以怎么操作呢？
思路
通用的思路，我们来模拟一下如何进行加法运算。
我们可以知道，加法可能会有进位。
那进位能不能判断还不好说（很麻烦），所以我们考虑在数组中逆序存储，这样如果有进位会在结果的后面存储，最后输出时再 逆序输出 ，就实现了存储。
为了方便，我建议大家把数组的每一位设置为0，可能会方便些。
比如说，我们要计算 。首先从用户那里输入进来，我们的字符串 、 的内容分别为 、。逆序存入数组储存：
然后，从0开始，遍历长度较长的数组，加法运算。
接下来，处理进位，逢十进一，当前的位取个位，后面的一位增加 。
从第 位倒着往回遍历，遇到第一个不是0的数时，就开始输出，得到 。
哈哈哈，惊不惊喜，意不意外？
加法的代码实现
如下是刚才我手写的程序，大家可以看看；
// Author:PanDaoxi
#include <bits/stdc++.h>
using namespace std;
// 用户输入的字符串
string s1,s2;
// a储存逆序s1，b储存逆序s2，c储存结果（考虑到进位，为了保证不会越界，开502的长度）
int a[501],b[501],c[502];
int main(){
cin>>s1>>s2;
// 逆序存入数组
for(int i=0;i<s1.size();i++) a[i]=s1[s1.size()-i-1]-'0';
for(int i=0;i<s2.size();i++) b[i]=s2[s2.size()-i-1]-'0';
// 加法计算
int maxlen=max(s1.size(),s2.size()); // 获取较长的长度
for(int i=0;i<maxlen;i++){
c[i]+=a[i]+b[i];
// 处理进位，不进位也不会受到影响
c[i+1]+=c[i]/10, // 如果不进位，就不会加
c[i]%=10; // 只取个位
}
// 获取第一个不是0的数
bool flag=false; // 标记是否找到第一个不是0的数
for(int i=maxlen+1;i>=0;i--){
if(c[i]||flag) flag=true; // 如果后面的一位不是0，就找到了第一个不是0的数；或者是已经找到了不是0的数，后面有0
if(flag) cout<<c[i]; // 如果已经找到了第一个不是0的数，就连续地输出
}
if(flag==false) cout<<0; // 如果到最后一位也没找到不是0的数，结果是0
return 0;
}
附上我以前初学时写的程序（可能过不了这个题，但是也是高精度），还是比较简单的：
// Author:PanDaoxi
#include <iostream>
using namespace std;
int main(){
// 高精度加法 240位内
int a[241]={},b[241]={},result[242]={},x=0,y=0;
string c,d;
cin>>c>>d;
// 第一步读取整数
for(int i=c.size()-1;i>=0;i--){
a[x++]=c[i]-'0';
}
for(int i=d.size()-1;i>=0;i--){
b[y++]=d[i]-'0';
}
// 第二步加法计算
for(int i=0;i<(x>y?x:y);i++){
result[i]+=(a[i]+b[i])%10;
result[i+1]+=(a[i]+b[i])/10;
}
for(int i=(x>y?x:y);i>=0;i--){
cout<<result[i];
}
return 0;
}
减法
减法和加法的算法差不太多，可以这样，你看，我们计算 ，可以这样：
我们借一当十，模拟：
例如下标为0的地方，可以这样计算：
OK，那就正常写呗：
// Author:PanDaoxi
#include <iostream>
using namespace std;
int main(){
string s1,s2;
int a[241]={},b[241]={},result[241]={},k=0,t;
cin>>s1>>s2;
// 考虑几种特殊情况
if(s1==s2){ // 相等
cout<<0;
return 0;
}
// 后面的比前面的长，需要输出负号
if(s1.size()<s2.size()||s1.size()==s2.size()&&s1<s2){
cout<<"-";
swap(s1,s2);
}
// 存储数据
for(int i=0;i<s1.size();i++){
a[s1.size()-i-1]=s1[i]-'0';
}
for(int i=0;i<s2.size();i++){
b[s2.size()-i-1]=s2[i]-'0';
}
// 模拟竖式的算法
for(int i=0;i<(s1.size()>s2.size()?s1.size():s2.size());i++){
t=10-b[i]+a[i]+result[k++];
if(t<10) result[k]--; // 退位，在后面一位减去1
result[k-1]=t%10;
}
// 前面可能有0，从第一个不是0的数开始输出
for(int i=k-1;i>=0;i--){
if(result[i]>0){
t=i; // 记录第一个不是0的数的下标
break;
}
}
// 输出
for(int i=t;i>=0;i--){
cout<<result[i];
}
return 0;
}
乘法
这次，有点儿难度。
例题1：
例题2：
高精度乘单精度
高精度乘单精度，有个高级用法，即幂运算。
咳咳先别说那么多，该怎么算啊？？
假设我们要计算 ，给定高精度数s1（123）和单精度n（5)，我们需要将高精度的每一位都乘上n，循环一遍；然后再处理进位。
// Author:PanDaoxi
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,a[501]={};
string s1;
cin>>s1>>n;
for(int i=0;i<s1.size();i++) a[i]=s1[s1.size()-i-1]-'0';
for(int i=0;i<s1.size()+5;i++){
// 按位相乘
a[i]*=n;
}
for(int i=0;i<s1.size()+5;i++){
// 处理进位
a[i+1]+=a[i]/10,a[i]%=10;
}
// 输出
bool flag=false;
for(int i=s1.size()+5;i>=0;i--){
if(a[i]||flag) flag=true;
if(flag) cout<<a[i];
}
if(!flag) cout<<0;
return 0;
}
我初学的时候这么写的：
// Author:PanDaoxi
#include <iostream>
using namespace std;
int main(){
// 高精度乘单精度（不超过10000）
int a[251]={};
string s1;
int b;
cin>>s1>>b;
for(int i=0;i<s1.size();i++){
a[i]=s1[s1.size()-i-1]-'0';
}
// 按位相乘
for(int i=0;i<s1.size();i++){
a[i]=a[i]*b;
}
// 处理进位
for(int i=0;i<s1.size()+4;i++){
if(a[i]>=10){
a[i+1]+=a[i]/10;
a[i]%=10;
}
}
// 获取第一个不是0的数
int point=0;
for(int i=s1.size()+4;i>=0;i--){
if(a[i]!=0){
point=i;
break;
}
}
for(int i=point;i>=0;i--){
cout<<a[i];
}
return 0;
}
高精度乘高精度
这个部分比较难，计算高精度数、的乘积，即
按照正常的竖式计算法，我们应该用一个数去乘另一个数的每一位（单精度），所以我们需要双重循环。
// AUTHOR:PANDAOXI
#include <iostream>
using namespace std;
int main(){
string s1,s2;
int a[4002]={},b[4002]={},result[8004]={};
cin>>s1>>s2;
for(int i=0;i<s1.size();i++) a[i]=s1[s1.size()-i-1]-'0';
for(int i=0;i<s2.size();i++) b[i]=s2[s2.size()-i-1]-'0';
for(int i=0;i<s1.size();i++){
for(int j=0;j<s2.size();j++){
result[i+j]+=a[i]*b[j];
result[i+j+1]+=result[i+j]/10,
result[i+j]%=10;
}
}
int p=0;
for(int i=s1.size()+s2.size()-1;i>=0;i--){
if(result[i]>0){
p=i;break;
}
}
for(int i=p;i>=0;i--){
cout<<result[i];
}
return 0;
}
解例题
第一题，我们可以使用高精度乘单精度，单精度即2，高精度即2的幂。
// Author:PanDaoxi
#include <iostream>
using namespace std;
int main(){
// 2的0次方=1
int a[501]={1},len=1,p,n; // len=1,记录长度
cin>>n;
for(int i=0;i<n;i++){ // 乘n次2
// 按位相乘
for(int j=0;j<len;j++){
a[j]*=2;
}
// 处理进位
for(int j=0;j<len;j++){
a[j+1]+=a[j]/10;
a[j]%=10;
}
// 如果后面有个数，长度就要增加了
if(a[len]>0) len++;
}
// 输出
for(int i=len;i>=0;i--){
if(a[i]>0){
p=i;
break;
}
}
for(int i=p;i>=0;i--){
cout<<a[i];
}
return 0;
}
说实话这个题根本用不着高精度，只是看着像，用高精度也能解。
// Author:PanDaoxi #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; cout<<(1<<n); // 左移一位（位运算） return 0; }
例题二也不难，高精度乘高精度，直接套程序。注意观察数据范围。
高精度除法
计算（保留n位小数）。大家可以找找规律。
// Author:PanDaoxi
#include <iostream>
using namespace std;
int main(){
int a,b,n,t=0,c[1001];
cin>>a>>b>>n;
// 输出小数点
cout<<a/b<<".";
a=(a%b)*10;
// 计算小数点后的数
for(int i=0;i<n;i++){
c[t++]=a/b;
a=(a%b)*10; // 当10，再算
}
// 输出
for(int i=0;i<t;i++){
cout<<c[i];
}
return 0;
}
关于打表
其实，告诉大家个坏消息，python自带高精度，C++就得手写……
例如这道题：
在竞赛中，Python可以当做工具使用，但不能作为程序提交。所以，我们可以结合Python（或其他语言、程序），把得到的结果储存在字符串数组中，这种行为就是打表。
打表虽然不讲武德，但是也有很多好处，我们要善于利用工具😅，尽管这可能对我们的学习好处并不很大。
这是表的生成器。
# Author:PanDaoxi
result = ""
for i in range(0,50):
s, d = 0, 1
for i in range(1, i+1):
d *= i
s += d
result += "\"" + str(s) + "\","
with open("test.txt", "w", encoding="utf-8") as f:
f.write(result)
运行后，生成test.txt，里面的内容放到字符串数组里，输入n，然后直接从数组里输出下标。多香啊！！
建议在提交题目时，把生成器写到注释里。
// Author:PanDaoxi
#include <iostream>
using namespace std;
int main(){
string s[51]={"0","1","3","9","33","153","873","5913","46233","409113","4037913","43954713","522956313","6749977113","93928268313","1401602636313","22324392524313","378011820620313","6780385526348313","128425485935180313","2561327494111820313","53652269665821260313","1177652997443428940313","27029669736328405580313","647478071469567844940313","16158688114800553828940313","419450149241406189412940313","11308319599659758350180940313","316196664211373618851684940313","9157958657951075573395300940313","274410818470142134209703780940313","8497249472648064951935266660940313","271628086406341595119153278820940313","8954945705218228090637347680100940313","304187744744822368938255957323620940313","10637335711130967298604907294846820940313","382630662501032184766604355445682020940313","14146383753727377231082583937026584420940313","537169001220328488991089808037100875620940313","20935051082417771847631371547939998232420940313","836850334330315506193242641144055892504420940313","34289376947494122614363304694584807557656420940313","1439295494700374021157505910939096377494040420940313","61854558558074209658512637979453093884758552420940313","2720126133346522977702138448994068984204397080420940313","122342346998826717539665299944651784048588130840420940313","5624964506810915667389970728744906677010239883800420940313","264248206017979096310354325882356886646207872272920420940313","12678163798554051767172643373255731925167694226950680420940313","620960027832821612639424806694551108812720525606160920420940313",};
int n;
cin>>n;
cout<<s[n];
return 0;
}
呵呵，羡慕吗？可惜竞赛不支持Python！