概念

之前做题，有时候会听到老师说：“这道题数据很大，要高精度。”

有些题的数据范围可以毒瘤到连开挂神器 __int128 都救不了你，这个时候我们就会选择：

让电脑跟我们人一样计算！毕竟人只要时间够，不管多大的数都是可以算出来的。

这就是高精度算法。

高精度的那些板子计算

说句闲话：高精度算法需要使用到 $string$ 类型的字符串，这里不提，请自行 BDFS。

1.高精度加法

要做高精度，首先需要了解人是怎么算的。

小学一年级内容出现了！（雾，大雾，伦敦雾

$$\ \ \ \ \ \ \ \ \ \ 3\ 2\ 8$$
$$+\ \ \ \ \ \ \ 1\ 3\ 7$$

$$\ \ \ \ \ \ \ \ \ \ 4\ 6\ 5$$

先看以上算式：

第一步：从低位往高位算，$8+7=15$。末位为5，往前进一位。

ans 0 1 5

第二步：算十位，$2+3+1=6$（1为进位），十位为6，不进位。

ans 0 6 5

第三步：算最高位，$3+1=4$，最高位为4。

ans 4 6 5

ans就是最终的答案了。

但是有个问题：上面这个例子两个加数的位数是一样的，那要是不一样呢？程序不就弄错了吗？

解决方法很简单：把两个加数倒着存就行了，这样因为数组初始化的原因，后面的数都会变成0，即会在前面自动补0。最后算出来的答案也是倒着的，再进行处理。

具体过程如下：(没错我又在水博客了，巨佬们直接跳过吧【滑稽】)

1.倒序存储

1
2
3
a 8 2 3
b 7 3 1
c 0 0 0

2.算第一位，进位直接存在下一位中
1
2
3
a 8 2 3
b 7 3 1
c 5 1 0

3.继续算，记得加上数组里本来就有的值（即进位）
1
2
3
a 8 2 3
b 7 3 1
c 5 6 0

4.一直循环，直到最后算完出结果
1
2
3
a 8 2 3
b 7 3 1
c 5 6 4

5.把答案倒过来输出
1
5 6 4 --> 465

这样就是一个不完整的高精度加法的过程。

为什么不完整呢？因为程序可能会在计算位数的时候出错（程序会把和的位数计算为加数中位数较大的那一个数的位数+1，但是不一定会进位），所以在结束计算之后，需要判断和的第一位是否为0，如果是就需要去除。

这就完整了！

最后给出一份有注释的高精度加法板子代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
int a[5005],b[5005],c[5005];//定义全局，即初始化为0 
string add(string a1,string b1){
    //前置工作 
    string c1;
    int lena=a1.size();
    int lenb=b1.size(); 
    //倒序存储并转换为整数类型 
    for(int i=0;i<lena;i++){
        a[lena-i]=a1[i]-'0';
    }
    for(int i=0;i<lenb;i++){
        b[lenb-i]=b1[i]-'0';
    }
    //做加法
    int lenc=1;
    //做加法的次数为两个高精度数中较大的位数 
    while(lenc<=lena||lenc<=lenb){
        c[lenc]+=a[lenc]+b[lenc]; //加法 
        c[lenc+1]=c[lenc]/10;     //进位 
        c[lenc]%=10;              //取个位 
        lenc++; 
    } 
    //去除前导0
    if(!c[lenc])
        lenc--;
    //把c存到c1里面
    while(lenc>=1)
        c1+=c[lenc--]+'0';
    return c1;
}
int main(){
    string a1,b1;
    cin>>a1;
    cin>>b1;
    cout<<add(a1,b1);
    return 0;
}

2.高精度减法

思路和高精度加法差不多，就是把进位换成退位，每次退位就让当前位数上的数加上10，然后让前面那个位数的答案-1。要注意前导0可能不止一个，需要连续去除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
int a[5005],b[5005],c[5005];
string sub(string a1,string b1){
    //前置工作
    if(a1==b1)
        return "0";
    string c1;
    int lena=a1.size();
    int lenb=b1.size();
    //倒序存储并转换为整数类型 
    for(int i=0;i<lena;i++){
        a[lena-i]=a1[i]-'0';
    }
    for(int i=0;i<lenb;i++){
        b[lenb-i]=b1[i]-'0';
    }
    //做减法
    int lenc=1;
    //做减法的次数为两个高精度数中较大的位数 
    while(lenc<=lena||lenc<=lenb){
        c[lenc]+=a[lenc]-b[lenc]; //减法
        if(c[lenc]<0){            //退位
            c[lenc]+=10;      //借位
            c[lenc+1]=-1;     //前面的要-1
        }
        lenc++;
    }
    //去除前导0
    while(!c[lenc])
        lenc--;
    //把c存到c1里面
    while(lenc>=1)
        c1+=c[lenc--]+'0';
    return c1;
}
int main(){
    string a1,b1;
    cin>>a1;
    cin>>b1;
    cout<<sub(a1,b1);
    return 0;
}

3.高精度乘法

这个就有点意思了。

再来看一个竖式：

$$\ \ \ \ \ \ \ \ 1\ 5\ 3$$
$$\times\ \ \ \ \ \ \ \ 2\ 7$$

$$\ \ \ \ \ \ 1\ 0\ 7\ 1$$
$$\ \ \ 3\ 0\ 6$$

$$\ \ \ \ \ \ 4 \ 1\ 3\ 1$$

乘法又是怎么算的呢？

根据日常经验，我们能很快发现：需要先将一个数拆掉，一位一位去乘另一个数，然后把结果加起来，不过加起来的时候需要乘以10^{最小位数-1}。

那事情就变得容易了起来，一个双重循环，每一次循环让被拆掉的那个数的每一位乘以另一个数，加在答案里，进位和加法差不多，不过要注意进位可能不止一位。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
int a[5005],b[5005],c[10005];
string mul(string a1,string b1){
    //如果有数为0直接返回0 
    if(a1=="0"||b1=="0")
        return "0";
    //前置工作
    string c1;
    int lena=a1.size();
    int lenb=b1.size();
    //倒序存储并转换为整数类型 
    for(int i=0;i<lena;i++){
        a[lena-i]=a1[i]-'0';
    }
    for(int i=0;i<lenb;i++){
        b[lenb-i]=b1[i]-'0';
    }
    //做乘法
    int lenc;
    for(int i=1;i<=lena;i++){
        for(int j=1;j<=lenb;j++){
            lenc=i+j-1;            //存进去的位数 
            c[lenc]+=a[i]*b[j];    //乘法 
            c[lenc+1]+=c[lenc]/10; //进位 
            c[lenc]%=10;           //取个位 
            lenc++;
        }
    }
    lenc=lena+lenb;
    //去除前导0 
    while(!c[lenc])
        lenc--;
    //把c存到c1里面
    while(lenc>=1)
        c1+=c[lenc--]+'0';
    return c1;
}
int main(){
    string a1,b1;
    cin>>a1;
    cin>>b1;
    cout<<mul(a1,b1);
    return 0;
}

4.高精度除法之高精除以低精

没学高精度之前一直不知道为什么要把除法分成两个部分，学了之后才发现这难度根本不是一个级别的！awa

首先还是思考人是怎么列竖式做除法的。你们自己脑补一个竖式吧。(ˉ▽ˉ；)…

做除法的步骤是：

  1. 用现在判断到这一位之前的数除以除数，把商存在答案中；
  2. 计算余数；
  3. 循环1~2，直到判断完毕。

这应该是一个很正确的思路，但是其实它本来是对的，但是放到程序里就错了。

为什么呢？

首先除以除数（第一步）的代码是这个样子的：

1
c[i]=(a[i]+c[i])/b;

第二步求余数的代码是这个样子的：

1
c[i+1]=(a[i]+c[i])%b*10;

很容易注意到，在执行第一步操作的时候，$c[i]$的值会发生改变，但是求余数需要用到的$c[i]$却必须是原来的值。

所以在代码的实现中，要先求余数再求商。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
int a[10005],b,c[10005];
string div(string a1,int b){
    if(a1=="0")
        return "0";
    //前置工作
    string c1;
    int lena=a1.size();
    //转换为整数类型 
    for(int i=0;i<lena;i++){
        a[i+1]=a1[i]-'0';
        //printf("%d",a[i+1]);
    }
    //除法
    for(int i=1;i<=lena;i++){
        /*
        ※错点：一定要先求下一位余了多少再求现在的位数，
        因为求现在的位数时c[i]的值会更新 
        */ 
        c[i+1]=(a[i]+c[i])%b*10; //求下一位余了多少 
        c[i]=(a[i]+c[i])/b;      //计算当前位数的值 
    } 
    int lenc=1;
    while(!c[lenc])
        lenc++;
    for(int i=lenc;i<=lena;i++)
        c1+=c[i]+'0';
    return c1;
}
int main(){
    string a1;
    cin>>a1;
    scanf("%d",&b);
    cout<<div(a1,b);
    return 0;
}

5.高精度除法之高精除以高精

emmm……

直到现在我的高精除高精还是没写出来啊╮(╯▽╰)╭，因为我感觉这个程序不是bug太多，而是整个程序就是一个bug……

先看思路。

首先高精除高精是不能像低精除法那样直接除的（不然请你告诉我怎么除），这里采取的方式是：用减法模拟除法。

设置一个变量$flag$，代表现在判断到了第几位。在这一位以及这一位之前组成的数就是被减数，除数就是减数。判断一下两个数之间还能否相减（即被减数是否还大于减数），如果不行了就判断下一位，如果还可以就继续减，直到不能减为止。

说得简单，这玩意儿实现起来超级无敌难的。

我的代码一直都是 $\texttt{TLE}\ 10$ 分，不过思路应该是对的，也拿出来给大家看一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//一个bug比头发还多的高精除高精代码 
#include<bits/stdc++.h>
using namespace std;
int a[5005],b[5005],c[5005],d[5005];
//这是判断是否还能减的函数 
bool check(int flag,int lena,int lenb){
    if(flag<lenb)
        return false;
    int sum=0;//统计前面有多少个前导0 
    for(int i=lena;i>=flag;i--){
        if(!a[i])
            sum++;
        else
            break;
    }
    if(flag-sum<lenb)
        return false;
    if(flag-sum>lenb)
        return true;
    //对于位数一样的数，判断是否可减
    bool f=1;//是否完全相等 
    for(int i=lena-sum;i>=1;i--){
        if(a[i]>b[i])
            return true;
        if(a[i]!=b[i])
            f=0;
    }
    if(f)
        return true;
    else
        return false;
}
string div(string a1,string b1){
    //前置工作
    if(a1=="0")
        return "0";
    string c1;
    int lena=a1.size();
    int lenb=b1.size();
    //倒序存储并转换为整数类型 
    for(int i=0;i<lena;i++){
        a[lena-i]=a1[i]-'0';
    }
    for(int i=0;i<lenb;i++){
        b[lenb-i]=b1[i]-'0';
    }
    //开始用减法模拟除法
    int flag=lena;//指针，现在到第几位了 
    int lenc=1;
    while(flag){
        //printf("%d\n",flag);
        if(!check(flag,lena,lenb)){//现在a已经小于b，需要进行下一位的除法 
            a[flag]=0;
            flag--;
            continue;
        }else{//a还未小于b，继续减 
            memset(d,0,sizeof(d));
            int lend=flag;
            while(lend<=lena||lend<=lenb){
                d[lend]+=a[lend]-b[lend];
                if(d[lend]<0){
                    d[lend]+=10;
                    d[lend+1]=-1;
                }
                lend++;
            }
            lenc++;
            for(int i=flag;i<=lena;i++)
                a[i]=d[i];
        }
    }
    //去除前导0
    while(!c[lenc])
        lenc--;
    //把c存到c1里面
    while(lenc>=1)
        c1+=c[lenc--]+'0';
    return c1;
}
int main(){
    string a1,b1;
    cin>>a1;
    cin>>b1;
    cout<<div(a1,b1);
    return 0;
}

（我那个 $10$ 分估计是特判 $0$​ 得的？）