洛谷 P2142 高精度减法

缘起

学习大整数高精度减法

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
题目描述
高精度减法

输入格式
两个整数a,b（第二个可能比第一个大）

输出格式
结果（是负数要输出负号）

输入输出样例

输入 #1 复制
2
1

输出 #1 复制
1

说明/提示
20% 数据 a,b在long long范围内

100% 数据 0 < a,b <= 10^{10086}
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include "stdafx.h"

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>

#define LOCAL
typedef long long LL;

using namespace std;

class bigint // 大整数类
{
public:
	bigint(LL a) // 用long long新建bigint, 注意, long long 的范围是 10^19, 而且科学计数法的最高位还是9, 这就是为什么我们要选择long long 作为大整数的一节的原因. 因为做大整数乘法的时候 10^9*10^9=10^18 也不会超出long long 的范围
	{
		while(a) num.push_back(a%BASE),a/=BASE;
	}

	bigint(){};

	bigint(string s) // 用 字符串 构造大整数, 例如输入的字符串是 "1034004543543", 我们要将其存储为  004543543-->1034, 其中num[0]=004543543, num[1] = 1034
	{
		int n = s.length();
		for (int i = n-1; i>=0; i-=BASE_LEN)
		{
			int j = max(0, i-BASE_LEN+1); // 则参与本次vector节点构建的字符是[j,...,i]
			LL t = 0;
			while(j<=i)
			{
				t = t*10+s[j]-'0'; // 洪特规则, 求出[j,...,i]表示的long long
				j++;
			}
			num.push_back(t);
		}
	}

	string toString() // 将大整数转为字符串输出(方便结果输出)
	{
		stringstream ss;
		bool flag = true; // 是否在输出vector的栈顶元素? (它是大整数的最高位部分)
		while(!num.empty())
		{
			if (flag)
			{
				ss << num.back();
				flag = false;
			}
			else
			{
				ss << setw(BASE_LEN) << setfill('0') <<num.back(); // 熟练使用STL 能极大减少编码的复杂度(而且看上去会很优雅)
			}
			num.pop_back();
		}
		return ss.str();
	}

	static bigint add(const bigint &a, const bigint &b) // 大整数加法 a+b, 其实就是小学生加法, 复杂度是O(n)的, 比字符串版本的大整数加法要快, 因为这里使用BASE_LEN作为一节, 所以其实一次做9位数加法（而且long long相加很快）, 即常数优化的.效率更高
	{
		bigint ans;
		for (LL i =0, carry=0; ; i++) // 注意, 大整数的结构是 num 的栈顶元素存储高位, 所以要从低位相加, carry 是上一步相加结果的进位(即i-1)
		{
			if (!carry && i>=a.num.size() && i >= b.num.size()) break; // 如果a和b都没有弹药了, 而且上一步并没有发生进位
			if (i<a.num.size()) // 如果a还有弹药
			{
				carry += a.num[i];
			}
			if (i<b.num.size()) // 如果b还有弹药
			{
				carry += b.num[i];
			}
			ans.num.push_back(carry%BASE);
			carry /= BASE; // 作为a.num[i+1]和b.num[i+1]的进位
		}
		return ans;
	}

	static bigint substract(bigint &a, bigint &b) // 高精度减法 a-b, 这里假设 a>=b
	{
		bigint ans;
		unsigned int i; // 注意, 因为size() 返回的是无符号整数, 所以这里最好使用unsigned int
		for (i = 0; i<b.num.size();i++)
		{
			ans.num.push_back(a.num[i]-b.num[i]); // 可能为负值
		}
		for (; i<a.num.size();i++)
		{
			ans.num.push_back(a.num[i]); // 把a剩下的塞进去
		}
		for (i = 0; i<ans.num.size()-1;i++) // 从ans的低位开始扫描负值, 即处理小学生减法之借位
		{
			if (ans.num[i]<0)
			{
				ans.num[i]+=BASE;
				ans.num[i+1]--; // 借位
			}
		}
		while(!ans.num.back()) // 删除无意义的前导0,注意,a=b的话,这里会报错,所以只能在a>b的时候用
		{
			ans.num.pop_back();
		}
		return ans;
	}

	int cmp(const bigint &b) const // 大于b返回1, 等于b返回0,小于b返回-1
	{
		if (num.size() != b.num.size())
		{
			return num.size()< b.num.size()?-1:1;
		}
		for (int i = num.size()-1; ~i; i--)
		{
			if (num[i]!=b.num[i])
			{
				return num[i]<b.num[i]?-1:1;
			}
		}
		return 0;
	}

private:
	const static int BASE_LEN=9,BASE=1000000000;// 10亿为基数
	vector<LL> num; // 构建大整数是这样的, 比如1034004543543, 在我们的bigint类中存储为  004543543-->1034, num[0]=004543543, num[1] = 1034
};


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	string a, b;
	cin >> a>>b;
	bigint A(a), B(b);
	int ret = A.cmp(B);
 	if (!ret) // a==b
	{
		cout<<"0";
	}
	else if (ret<0) // a<b
	{
		cout << "-" << bigint::substract(B,A).toString();
	}
	else // a>b
	{
		cout << bigint::substract(A,B).toString();
	}
	return 0;
}

ac情况

评测状态 Accepted