hdu 1002 A + B Problem II 高精度

缘起

高精度是算法的重要组成部分. 遂来写板子学习一下, 找到了板题 hdu 1002 A + B Problem II

分析

题意很裸

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
我有一个非常简单的问题。 给定两个整数A和B，你的工作是计算A + B的和。

【输入】
输入的第一行包含整数T（1 <= T <= 20），表示测试用例的数量。 然后是T行，每行包含两个正整数，A和B.请注
意，整数非常大，这意味着您不应该使用32位整数来处理它们。 您可以假设每个整数的长度不超过1000。

【输出】
对于每个测试用例，您应输出两行。 第一行是“Case＃：”，＃表示测试用例的编号。 第二行是方程“A + B = 
 Sum”，Sum表示A + B的结果。注意方程中有一些空格。 在两个测试用例之间输出一个空行。
 
【样例输入】
2
1 2
112233445566778899 998877665544332211
    
【样例输出】
Case 1:
1 + 2 = 3

Case 2:
112233445566778899 + 998877665544332211 = 1111111111111111110

就是小学生加法. 但是做了常数优化——不采用字符串模拟大数加法, 而是使用 long long 来模拟

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
//#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;
	}


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


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	for (int i =1;i<=t;i++)
	{
		if (i>1) puts("");
		printf("Case %d:\n", i);
		string a,b;
		cin >> a >> b;
		bigint A(a), B(b);
		cout << A.toString() << " + " << B.toString() << " = " << bigint::add(A,B).toString() << endl;
	}
	return 0;
}

ac 情况

Status Accepted
Time 15ms
Memory 1832kB
Length 2357
Lang C++
Submitted 2019-08-07 22:20:32
Shared
RemoteRunId 30160117