大整数减法

题意

给定 $a>b$ 的两个不超过 $200$ 位正整数，输出 $a-b$ 。

思路

Python 的 int 不受 C++ 基础整数位数限制，直接读入并相减即可，借位与前导零由运行时处理。

代码

Python代码

python

1
2
3minuend = int(input())
subtrahend = int(input())
print(minuend - subtrahend)

C++代码

cpp

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#include <cstdio>
#include <cstring>


char num_1[300];
char num_2[300];
int num_3[300] = {0};

int main(){
    scanf("%s",num_1);
    scanf("%s",num_2);
    int len_1 = strlen(num_1);
    int len_2 = strlen(num_2);
    int i,j;

    for(i=0;i<len_1/2;i++){
        char t = num_1[i];
        num_1[i] = num_1[len_1 -i -1];
        num_1[len_1 -i -1] = t;
    }
    for(i=0;i<len_2/2;i++){
        char t = num_2[i];
        num_2[i] = num_2[len_2 -i -1];
        num_2[len_2 -i -1] = t;
    }
    for (i=0;i<len_1;i++){
        num_1[i] -= '0';
    }

    for (i=0;i<len_2;i++){
        num_2[i] -= '0';
    }

    int max_len = len_1;
    if( max_len < len_2){
        max_len = len_2;
    }
    for (i=0;i<max_len;i++){
        if( num_1[i] < num_2[i]){
            num_1[i+1]--;
            num_3[i] = 10+num_1[i] - num_2[i];
        }
        else {
            num_3[i] = num_1[i] - num_2[i];
        }
    }

    bool is_begin_0 = true;
    for(i = max_len ;i>=0;i--){
        if( is_begin_0 && num_3[i] == 0) continue;
        is_begin_0 = 0;
        printf("%d",num_3[i]);
    }
    if( is_begin_0 )
        printf("0");

    return 0;
}

复杂度

设数字位数为 $d$ ，时间复杂度和额外空间复杂度均为 $O(d)$ 。

总结

语言自带任意精度时，应把精力放在题目逻辑而不是重复实现借位。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结