高精度问题

高精度主要是解决处理大整数时的问题，这里的整数范围要超过longlong。
高精度问题的核心就是使用字符串去模拟加法、减法、乘法、除法运算

高精度加法

基本

使用三个数组a[],b[],c[]存储
模拟加法竖式：累加 进位 留位

  • 累加： c[i] += a[i] + b[i] ——>必须要累加之前的进位，使用 += //累加进位和对应位置的数字

  • 进位：c[i+1] = c[i] / 10;

  • 留位：c[i] %= 10;

Q1：假设正整数A的长度为n,正整数B的长度为m，那么A+B的长度最大为多少？最小为多少？

  • A1： 长度最大：max(n,m)+1 长度最小：max(n,m)

算法步骤

  1. 高精度数的读取与存储：使用字符串方式读取，然后将每一个字符转为整数，逆向存储到一个整型数组中
  2. 模拟加法操作：通过数组下标模拟两个加数中每一个为上数的加法（累加、进位、留位）
  3. 去除前导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
// a,b数组用于存储A,B两个加数，c数组用于存储相加之和
int a[200+10],b[200+10],c[200+10];

string Add(string as,string bs){
    //清空a,b,c数组
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));

    //求出as bs字符串的长度
    int alen = as.size(),blen = bs.size();
    int clen = max(alen,blen) + 1;

    //将字符串转为整型数组，并且逆向存储
    for(int i=1; i<=alen; i++)
        a[i] = as[alen - i] - '0';
    for(int i=1; i<=blen; i++)
        b[i] = bs[blen - i] - '0';

    //模拟加法计算：累加 进位 留位
    for(int i=1; i<=clen; i++){
        c[i] += a[i] + b[i];    //一定要使用'+='累加进位
        c[i+1] = c[i]/10;   //进位
        c[i] = c[i]%10;     //留位
    }

    //去除前导0
    //clen>1：如果只有一位数字0要保留，所以只到第二位
    while(c[clen] == 0 && clen>1)
        clen--;

    //逆向重组
    string cs = "";
    for(int i=clen;i>=1;i--){
        cs += c[i] + '0';
    }

    return cs;
}

高精度减法

基本

  1. 如果a[i] < b[i] ：说明a[i] 需要向a[i+1]借位：
    1
    2
    a[i+1]--;
    a[i]+=10;
  2. 模拟减法：c[i] = a[i] - b[i];
  3. 高精度减法的程序计算中都默认a 是大于 b来计算的，如果实际情况是a < b，那么只需要交换一下a，b即可
  4. 下面提到的a、as都是指减法运算中较大的那一个（被减数），b、bs同理都是值减数

Q1: 如果a[i+1] == 0，这样借位会不会有问题

  • A1： 不会，因为最多只会借一位。a[i+1]被借位后等于-1，因为a>b(在模拟计算的算法中都转化为a>b来计算，后文详解)，a[i+1]还可以向a[i+2]借位。借位后a[i+1] == 9，而b[i+1]最大也才为9。

算法步骤

  1. 高精度数的读取与存储：使用字符串方式读取，然后将每一个字符转为整数，逆向存储到一个整型数组中
  2. 模拟减法计算：相同位置进行相减，不够减时向高位借位
  3. 去除前导0，再逆序输出

Q1：两个长整数a,b，并且a>b，长度分别为n,m，那么c = a-b的长度最长为多少？

  • A1：n

Q2：两个正整数字符串as,bs，如何判断as和bs的大小（也即a和b的大小）？

  • A2 ：if( as.size() < bs.size() || (as.size() == bs.size() && as < bs)) 成立，那么说明 as < bs ---> 长整数a < b

Q3：如果a<b，如何计算a-b的值呢？

  • A3： 交换a和b的值，然后计算a-b，结果输出一个负号

计算高精度减法函数

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
int a[200+10],b[200+10],c[200+10];
string Sub(string as,string bs){
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));

    string cs = "";
    //预处理，比较as和bs的大小，来确定正负号和决定是否交换
    // 处理后要求as比bs大，计算都默认as比bs大
    if(as.size() < bs.size() || (as.size() == bs.size() && as < bs)){
        cs += '-';  //结果字符串加一个负号
        as.swap(bs);
    }

    int alen = as.size(),blen = bs.size();
    int clen = alen;    //因为as是较大的数，

    //字符串转整型数组，逆序存储
    for(int i=1;i<=alen;i++)
        a[i] = as[alen - i] - '0';
    for(int i=1;i<=blen;i++)
        b[i] = bs[blen - i] - '0';
    //模拟减法
    for(int i=1;i<=clen;i++){
        //模拟a[i]向a[i+1]借位
        if(a[i]<b[i]){
            a[i+1]--;
            a[i] += 10;
        }
        c[i] = a[i] - b[i];
    }

    //去除前导0
    while(c[clen]==0 && clen>1) clen--;

    //逆向重组
    for(int i=clen;i>=1;i--){
        cs+=c[i] + '0';
    }

    return cs;
}

int main(){
    string as,bs,cs;
    getline(cin,as);
    getline(cin,bs);
    cs = Sub(as,bs);
    cout<<cs;

    return 0;
}

高精度乘法

基本

  1. 本质上还是使用字符串来模拟整数的乘法计算过程

$\qquad\qquad\qquad b_3 \qquad\qquad\qquad b_2 \qquad\qquad\qquad b_1$
$\times\qquad\qquad\qquad\qquad\qquad\qquad a_2 \qquad\qquad\qquad a_1$
$—————————————————————————$
$\qquad\qquad\qquad b_3\ast a_1 \qquad\qquad b_2\ast a_1 \qquad\qquad b_1\ast a_1$
$\quad b_3\ast a_1 \qquad b_2\ast a_1 \qquad\qquad b_1\ast a_1$
$—————————————————————————$
$\qquad c_4 \quad\quad\qquad c_3 \qquad\qquad\qquad c_2 \qquad\qquad\qquad c_1$

  1. 观察式子的下标可以发现 c[i+j-1] += a[i]*b[j]

高精度乘法算式的模拟

  1. 下面的模拟是按照乘法结果的每一行来模拟的，即先把 $a_1$ 与b相乘的加到c中去，再把 $a_2$ 与b相乘的加到c中去
1
2
3
4
5
6
7
for(int i=1;i<=alen;i++){
    for(int j=1;j<=blen;j++){
        c[i+j-1] += a[i]*b[j];  //前一项的进位也加在c[i+j-1]中
        c[i+j] += c[i+j-1] / 10;    //因为是要处理多行，所以可能会有多次进位
        c[i+j-1] %= 10;     //留位
    }
}

Q1：设整数A的长度为n，整数B的长度为m，那么A*B的长度最大为多少，最小为多少

  • A1： A*B的长度最长不会超过n+m，最短不会低于max(n,m)

算法步骤

时间复杂度O(n*m)

  1. 高精度数的读取与存储：使用字符串方式读取，然后将每一个字符转为整数，逆向存储到一个整型数组中
  2. 模拟乘法计算
  3. 去除前导0
  4. 逆序重组

高精度乘法函数

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
const int N = 210;
int a[N],b[N],c[N+N];
string Mult(string as,string bs){
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));

    string cs = ""; //不能写成string cs = " ";
    int alen = as.size(),blen = bs.size();
    int clen = alen + blen;
    // 字符串逆序转为整型数组
    for(int i=1;i<=alen;i++)
        a[i] = as[alen - i] - '0';
    for(int i=1;i<=blen;i++)
        b[i] = bs[blen - i] - '0';

    //模拟乘法算式
    for(int i=1;i<=alen;i++){
        for(int j=1;j<=blen;j++){
            c[i+j-1] += a[i]*b[j];
            c[i+j] += c[i+j-1] / 10;
            c[i+j-1] %= 10;
        }
    }

    while(c[clen] == 0 && clen>1)
        clen--;
    for(int i=clen;i>=1;i--){
        cs += c[i] + '0';
    }

    return cs;
}

高精度除法（长数/短数）

这里的高精度除法指的是一个长数（被除数）和一个短数（除数）做高精度除法

基本

  1. 将长数做字符串处理转为整数存入数组，但与高精度加减法和乘法不同，除法的长数不需要做逆向存储
  2. 模拟的过程是从长数的高位开始与除法进行除法与取模 
    1
    2
    3
    4
    5
    6
    int r=0;
    for(int i=1;i<=clen;i++){
        r = r*10 + a[i];    //构造被除数,依次称10进位
        c[i] = r/x; //得到商
        r %= x;    //除剩的余数再进入到下一轮除法
    }

Q1：设长整数A的长度为n，短整数B的长度为m，那么A/B的长度最大为多少，最小为多少

  • A1： A/B的长度最长不会超过n，最短为1

算法步骤

  1. 高精度数的读取与存储：使用字符串方式读取，然后将每一个字符转为整数，正向存储到一个整型数组中
  2. 从高位开始进行模拟除法计算
  3. 去除前导0
  4. 正序重组

高精度除法函数

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
const int N =10000+10;
int a[N],c[N];

string Div(string as,int x){
    memset(a,0,sizeof(a));
    memset(c,0,sizeof(c));

    int alen = as.size();
    int clen = alen;

    //正向存储
    for(int i=1;i<=alen;i++){
        a[i] = as[i-1] - '0';
    }

    int r=0;
    for(int i=1;i<=clen;i++){
        r = r*10 + a[i];
        c[i] = r/x;
        r %= x;
    }

    //去除前导0，但不到clen
    int k=1;
    while(c[k] == 0 && k<clen){
        k++;
    }

    string cs="";
    for(int i=k;i<=clen;i++){
        cs += c[i] + '0';
    }

    return cs;
}

求余数

同求商类似，最后只需要返回r即可

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
const int N =10000+10;
int a[N],c[N];

int Dremainder(string as,int x){
    memset(a,0,sizeof(a));
    memset(c,0,sizeof(c));

    int alen = as.size();
    int clen = alen;

    //正向存储
    for(int i=1;i<=alen;i++){
        a[i] = as[i-1] - '0';
    }

    int r=0;
    for(int i=1;i<=clen;i++){
        r = r*10 + a[i];
        c[i] = r/x;
        r %= x;
    }

    return r;
}