VIRTUALS

the virtual labs for the virtuals

0%

【AcWing算法基础】第一讲-基础算法-高精度 AcWing 792. 高精度减法

Posted on Edited on In , , , ,

摘要：
高精度减法模板题。

题目

给定两个正整数，计算它们的差，计算结果可能为负数。

输入格式
共两行，每行包含一个整数。

输出格式
共一行，包含所求的差。

数据范围
$1≤$ 整数长度$ ≤10^5$

输入样例：

32
11

输出样例：

21

注意这道题是两个正整数相减。
如果换成带负数的，进行判断正负之后，要么转化为两个正整数相加，要么依旧是两个正整数相减。

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool cmp(vector<int> &a, vector<int> &b)
{
    if (a.size() != b.size()) return a.size() > b.size();
    for (int i = a.size() - 1; i >= 0; i -- ) {
        if (a[i] != b[i]) return a[i] > b[i];
    }
    return true;
}

vector<int> sub(vector<int> &m, vector<int> &n) 
{
    vector<int> res;
    for (int i = 0, t = 0; i < m.size(); i ++ ) {
        t += m[i];
        if (i < n.size()) t -= n[i];
        res.push_back((t + 10) % 10);                                               // 1
        if (t < 0) t = -1;
        else t = 0;
    }
    for (;res.size() > 1 && res.back() == 0;) res.pop_back();                       // 2
    return res;
}

int main()
{
    string a, b;
    cin >> a >> b;
    vector<int> m, n;
    for (int i = a.length() - 1; i >= 0; i -- )  m.push_back(a[i] - '0');
    for (int i = b.length() - 1; i >= 0; i -- )  n.push_back(b[i] - '0');
    vector<int> res;
    if (cmp(m, n)) res = sub(m, n);
    else {
        res = sub(n, m);
        cout << '-';
    }
    for (int i = res.size() - 1; i >= 0; i -- ) cout << res[i];
    return 0;
}
  1. 此处t有可能被减成了负数（最低可以取到-10，最高可取到9），此时向后一位借10，于是最低取到0；同时由于借10的时候并没有判断正负，所以+10可能会导致结果高于10。也就是说，此时运算过程放入C中的数可能的取值范围是：(0, 19)。这样我对10取模，即可得到正确的放入C中的数了。
    注意，在把“优化”后的（指借位模10）运算结果放入C时，并没有把结果赋值给t，因为后面需要判断t的正负，以更新下一轮的t取值。如果赋值了，则t必然为正，无法更新进位信息。
  2. 注意当A与B前几位部分相等时，C后面会存在’0’，如123 - 120结果类似003。但在结果仅为1位时，不用考虑。

原题链接：AcWing 792. 高精度减法