前言
某同学：你为啥不写高精度呢？
我：那玩意儿有啥讲的，又不是啥重要的知识点。
某同学：万一要用呢？
我：……
我：那就等要用了再说。
好的前几天真写到要用高精度的题了。
我说我无中生题你信吗。
高精度
高精度这个东西，本质上就是一种模拟，它通过模拟人列竖式计算的过程来实现计算大数。
你比如说正常情况下我们有 int 和 long long 两种类型，实在不行还有 unsigned 和 __int128 类型。但是就算是 __int128，也只能计算 \(-2^{127}\sim2^{127}-1\) 之间的数，换算成十进制大概是 \(39\) 位。
那如果现在我要算 \(100\) 位、\(1000\) 位，甚至 \(10000\) 位的十进制加减乘除法怎么办呢？显然我们人在计算大数的加减乘除时用的是竖式，那我们可不可以模仿竖式的方法写出一套加减乘除法呢？
高精度加法、减法
首先讲最简单的高精度加法与减法。因为通过竖式我们能观察到：加法与减法本质上就是每一位对位相加减，唯一的问题是进位与借位。
搞懂这个东西的原理过后，那一切就都很简单了：我们只需要定义一个数组，然后让数组的每一位存一位数字，这样加法就是把每一位相加，减法就是把每一位相减。
现在来说说进位和借位。显然进位是从低位往高位进位，借位也是从低位往高位借位。所以我们只需要将整个数组从低位往高位循环一遍并做处理。
当然，如果说目前的最高位还能进位，那么我们就要适当扩展位数了。如果前面有过多的前导 \(0\)，也需要缩小位数。
为了更方便的扩展位数，我们一般会把最高位放在最后，而最低位放在最前面，也就是把整个数倒过来。
代码：
for(int i=1;i<=nc;i++)
{c[i]=a[i]+b[i];//减法改成 a[i]-b[i] 就行了if(c[i]>9)//进位{c[i+1]+=c[i]/10;c[i]%=10;}if(c[i]<0)//借位 {c[i+1]--;c[i]+=10;}
}
while(c[nc]>9)//高位进位
{c[nc+1]+=c[nc]/10;c[nc]%=10;nc++;
}
while(c[nc]==0&&nc>1)//去掉前导 0，nc>1 是防止答案是 0 时会去掉这个 0
{nc--;
}
高精度乘法
关于高精度乘法，显然我们也可以通过竖式找规律。这里跳过这一环节。
最终我们会发现：\(a_i\times b_j\) 的结果会被保存到 \(c_{i+j-1}\)（从 \(1\) 开始，如果从 \(0\) 开始就没有 \(-1\)），因此我们可以这么写：
for(int i=1;i<=na;i++)
{for(int j=1;j<=nb;j++){c[i+j-1]+=a[i]*b[j];//这里记得用 += if(c[i+j-1]>9)//进位 {c[i+j]+=c[i+j-1]/10;c[i+j-1]%=10;}}
}
while(c[nc]>9)//高位进位
{c[nc+1]+=c[nc]/10;c[nc]%=10;nc++;
}
显然是我已经懒得讲了。
高精度除法
高精度除法这个稍微有点难办了，因为虽然除法有一种理解方式就是被除数不断减去除数，但是你不知道答案有多大，因此我们还是要从竖式上入手。
我们会发现在竖式上，除法其实是先将当前的余数求出来，然后除以除数得到当前这一位的商，然后再计算当前这一位的余数继承到下一位，然后重复这个过程。
稍微有点抽象，我来举个例子手动具象化一下。比如你让算 \(12345\div5\) 等于多少，首先一开始你的余数是 \(0\)，然后将这个余数与你的第一位拼接在一起，就变成了 \(1\)，然后你发现 \(1\div5=0\) 余 \(1\)，所以第一位答案是 \(0\)，余数是 \(1\)。
接着你将余数 \(1\) 与第二位拼在一起，就成了 \(12\)，然后你发现 \(12\div5=2\) 与 \(2\)，所以第二位答案是 \(2\)，余数是 \(2\)。
接着你将余数 \(2\) 与第三位拼在一起，就成了 \(23\)，然后你发现 \(23\div5=4\) 余 \(3\)，所以第三位答案是 \(4\)，余数是 \(3\)。
接着你将余数 \(3\) 与第四位拼在一起，就成了 \(34\)，然后你发现 \(34\div5=6\) 余 \(4\)，所以第四位答案是 \(6\)，余数是 \(4\)。
接着你将余数 \(4\) 与第五位拼在一起，就成了 \(45\)，然后你发现 \(45\div5=9\) 与 \(0\)，所以第五位答案是 \(9\)，余数是 \(0\)。
因此我们得到最终答案：\(12345\div5=2469\) 余 \(0\)。
好的这样我们就把一个庞大的问题转化成了一个个小问题。现在唯一的问题是每一次除法我该怎么做？这个分两种情况。
高精除以低精
也就是说一个非常大的数除以一个非常小的数，这时每一次除法是可以直接计算的，因此每次算答案直接用当前余数除以除数就行了。
代码：
int v=0;
for(int i=na;i>=1;i--)
{v=v*10+a[i];//把之前余数与当前位拼接c[i]=v/b;//算商v%=b;//取余数
}
while(c[nc]==0&&nc>1)//去掉前导 0
{nc--;
}
高精除以高精
一般情况下上面那种已经够用了，但是不乏有些丧心病狂的出题人，非要让你写一个高精除以高精，这时该咋办呢？
显然，我们没法直接做除法，那我们可以把每次除法转化成另一种东西——减法。
我们再用一个高精度数存当前的余数，然后你会发现一开始的乘法和加法是好处理的。
接下来我们每次判断当前的余数是否大于等于除数，如果是那么就在答案当前位上加一，然后给余数减去一次除数，直到不满足条件为止。
因为每一位的数最大是 \(9\)，所以你的循环次数必然不会超过 \(10\) 次。
这个我好像没写过，大家可以尝试一下。
压位
压位算是高精度的一个技巧，要理解压位我们需要把高精度放在一个更高的角度来看。
从更高的角度来看：高精度实际上就是在模拟一次十进制计算，那如果我们将这个进制切换一下，对应到高精度上是什么呢？你会发现你每一位存的数都是按照这个新的进制来的，于是压位变诞生了。
我们会发现之前一位一位存储的方式效率太低了，那么我们可以直接从十进制变成十亿进制，也就是把进制从 \(10\) 改成 \(10^9\)，那么对应上去就是说：你把原本 \(9\) 位才能计算的东西缩小到了 \(1\) 位就能计算出来，因此总时间复杂度就会除以一个 \(9\) 的常数。
当然你可以把进制改成各种各样的，就会除以不同的常数。
代码我懒得给了，实际上就是把上面的代码修改一下进制就行了。