题目描述

给定两个正整数（不含前导 $0$），计算它们的差，计算结果可能为负数。

输入格式

共两行，每行包含一个整数。

输出格式

共一行，包含所求的差。

数据范围

$1≤整数长度≤10^5$

输入样例：

32
11

输出样例：

21

算法1

(高精度) $O(n)$

这道题的数字很大，所以我们要用高精度来做。

高精度减法过程：

具体实现过程见代码注释。

时间复杂度

参考文献

C++ 代码（无注释代码见高精度减法）

$STL$版本

#include <iostream>
#include <vector>
using namespace std;
bool cmp(vector <int> &A,vector <int> &B){ // 判断是否A ≥ B
    if(A.size() != B.size()) return A.size() > B.size(); // 如果A、B长度不相同，长度长的那个数大
    for(int i = A.size() - 1;i >= 0;i --){ // 否则就要从最高位开始看（因为执行这个函数前，A和B数组都已经倒序，所以这里要从后往前看）
        if(A[i] != B[i]) return A[i] > B[i]; // 如果A的当前位和B的当前位不相等，当前位大的更大
    }
    return true; // 如果A、B数组都相等，这里可以直接返回true，当然也可以直接输出0
}
vector <int> sub(vector <int> &A,vector <int> &B){ // A - B
    int t = 0; // 每一位上相减得到的数
    vector <int> C; // 最后的答案
    for(int i = 0;i < A.size();i ++){ // 遍历一遍，和高精度加法不一样的是，只要遍历完A就行了，因为这里A肯定比B长
        t = A[i] - t; // t要等于A的当前位减掉自己，因为上一位有可能出现借位的情况
        if(i < B.size()) t -= B[i]; // 如果没有遍历完B，那么t减掉B的当前位
        C.push_back((t + 10) % 10); // 更新C数组
        // 这里如果没有借位，(t + 10) % 10就刚好等于t
        // 如果这里有借位，(t + 10) % 10就会借一个10下来
        if(t < 0) t = 1; // 如果t < 0，说明不够减，需要借位，把t赋值为1，就是在下一次执行中，A的当前位会减掉t
        else t = 0; // 否则够减，赋值为0，不用借位
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back(); // 删除前导0
    return C; // 返回答案
}
int main(){
    string a,b; // 两个数，因为很大，所以用string来存
    cin>>a>>b; // 读入
    vector <int> A,B; // 两个数，因为减法是从最低位开始减，我们可以把两个数倒过来
    for(int i = a.size() - 1;i >= 0;i --) A.push_back(a[i] - '0'); // 把a数组到过来存入A，记得a是string类型的数组，要减去'0'让它变成数字
    for(int i = b.size() - 1;i >= 0;i --) B.push_back(b[i] - '0'); // 把b数组倒过来存入B
    if(cmp(A,B)){ // 如果A > B
        auto C = sub(A,B); // 那么可以直接相减
        for(int i = C.size() - 1;i >= 0;i --) printf("%d",C[i]); // 最后因为C是倒着的，需要反向输出
    }
    else{ // 否则A < B，需要计算-(B - A)
        auto C = sub(B,A); // 计算B - A
        printf("-"); // 给前面加上一个负号
        for(int i = C.size() - 1;i >= 0;i --) printf("%d",C[i]); // 反向输出C数组
    }
    return 0;
}

数组版本

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
string stra,strb;
int lena,lenb,lenc;
int a[N],b[N],c[N];
bool check(string a,string b){ // 判断数a是否大于等于数b
    if(lena != lenb) return lena > lenb; // 如果从位数就可以看出a和b的大小关系，直接判断
    // a和b的位数相同
    for(int i = 0;i < lena;i ++){ // 从最高位开始检查
        if(a[i] != b[i]) return a[i] > b[i]; // 如果两个数字不同，判断
    }
    return true; // 如果a=b，那么也是可以直接计算a-b的，但也可以直接输出0
}
void sub(int a[],int b[]){ // 高精度减法
    int t = 0; // 退位
    // 要注意，a的长度大于b的长度，所以下面遍历以a的长度为准
    for(int i = 1;i <= lena;i ++){ // 从最低位开始
        t = a[i] - t; // 计算退位，a数组中一定是有数的，但b数组中可能没有，所以说用a来计算退位
        if(i <= lenb) t -= b[i]; // 如果b数组还没遍历完，那么把b[i]减上
        c[++ lenc] = (t + 10) % 10; // 存储
        if(t < 0) t = 1; // 如果需要退位，将t赋值为1,（这个应该不需要解释吧）
        else t = 0; // 否则就没有退位，直接赋值为0
    }
    while(c[lenc] == 0 && lenc > 1) lenc --; // 去除前导0
    // 上面没讲去除前导0的过程，这里讲一下吧
    // 首先判断该位是否为0，不是那就可以退出循环，因为已经删到底了
    // 如果是0的话，删除这个0，这里只需要把c的长度减1，后面就不会输出了
    // 需要注意的是，如果a = b，也就是结果为0，需要留下一个0，所以有了lenc > 1，就是为了防止把所有的0都删掉
}
int main(){
    cin.tie(0);
    cin>>stra>>strb; // 读入
    lena = stra.size();
    lenb = strb.size();
    for(int i = 1;i <= lena;i ++) a[i] = stra[lena - i] - '0'; // 将stra，strb倒序存入数组a，b
    for(int i = 1;i <= lenb;i ++) b[i] = strb[lenb - i] - '0';
    if(check(stra,strb)){ // 如果数a大于数b，不需处理，直接计算
        sub(a,b);
    }
    else{ // 如果数a小于数b，那么说明结果是负数，需要提前输出负号
        // 如没有交换a和b的长度Wrong Answer第8个点
        swap(lena,lenb); // 注意！函数中相当于把数组a和b交换，那么a和b的长度也是需要交换的
        sub(b,a); // 反着传入高精度减法函数
        printf("-"); // 提前输出负号
    }
    for(int i = lenc;i >= 1;i --) printf("%d",c[i]); // 反向输出数组c，也就是结果，为什么要倒着输出和高精度加法是一样的
    return 0;
}

struct 数组模拟

我们可以把高精度减法的操作封装在 $struct$ 里，便于使用。

应该能看得出来每个函数在干什么，这里就不多做讲解。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
struct bignum{
    char s[N];
    int a[N],len;
    bool flag;
    bignum(){
        memset(a,0,sizeof a);
        len = 1;
        flag = 0;
    }
    bignum(int x){
        while(x){
            a[len] = x % 10;
            x /= 10;
            len ++;
        }
        len --;
    }
    int &operator [] (int i){
        return a[i];
    }
    friend bool operator < (bignum a,bignum b){
        if(a.len < b.len) return true;
        if(a.len > b.len) return false;
        for(int i = a.len;i >= 1;i --){
            if(a[i] < b[i]) return true;
            if(a[i] > b[i]) return false;
        }
        return false;
    }
    friend bool operator > (bignum a,bignum b){
        if(a.len < b.len) return false;
        if(a.len > b.len) return true;
        for(int i = a.len;i >= 1;i --){
            if(a[i] < b[i]) return false;
            if(a[i] > b[i]) return true;
        }
        return true;
    }
    friend bool operator == (bignum a,bignum b){
        if(a.len != b.len) return false;
        for(int i = a.len;i >= 1;i --){
            if(a[i] != b[i]) return false;
        }
        return true;
    }
    void input(){
        scanf("%s",s + 1);
        len = strlen(s + 1);
        for(int i = 1;i <= len;i ++) a[i] = s[len - i + 1] - '0';
    }
    void print(){
        if(flag) printf("-");
        for(int i = len;i >= 1;i --) printf("%d",a[i]);
    }
};
bignum operator - (bignum a,bignum b){
    bignum c;
    if(a < b){
        c.flag = 1;
        swap(a,b);
    }
    int t = 0;
    c.len = 0;
    for(int i = 1;i <= a.len;i ++){
        t = a[i] - t;
        if(i <= b.len) t -= b[i];
        c[++ c.len] = (t + 10) % 10;
        if(t < 0) t = 1;
        else t = 0;
    }
    while(c[c.len] == 0 && c.len > 1) c.len --;
    return c;
}
int main(){
    bignum a,b,c;
    a.input();
    b.input();
    c = a - b;
    c.print();
    return 0;
}