【洛谷】P1604 B进制星球

【洛谷】P1604 B进制星球

题目地址：

题目描述：
话说有一天，小 Z Z Z乘坐宇宙飞船，飞到一个美丽的星球。因为历史的原因，科技在这个美丽的星球上并不很发达，星球上人们普遍采用 B B B（ 2 < = B < = 36 2<=B<=36 2<=B<=36）进制计数。星球上的人们用美味的食物招待了小 Z Z Z，作为回报，小 Z Z Z希望送一个能够完成 B B B进制加法的计算器给他们。 现在小 Z Z Z希望你可以帮助他，编写实现 B B B进制加法的程序。

输入格式：
共 3 3 3行第 1 1 1行：一个十进制的整数，表示进制 B B B。第 2 − 3 2-3 2−3行：每行一个 B B B进制数正整数。数字的每一位属于 { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , A , B , . . . } {0,1,2,3,4,5,6,7,8,9,A,B,...} {0,1,2,3,4,5,6,7,8,9,A,B,...}，每个数字长度 < = 2000 <=2000 <=2000位。

输出格式：
一个 B B B进制数，表示输入的两个数的和。

高精度加法直接模拟即可。代码如下：

#include <iostream>
#include <algorithm>
using namespace std;int k;
string res;#define to_int(x) ('A' <= x && x <= 'Z' ? x - 'A' + 10 : x - '0')
#define to_char(x) (x <= 9 ? x + '0' : x - 10 + 'A')int main() {scanf("%d", &k);string a, b;cin >> a >> b;reverse(a.begin(), a.end());reverse(b.begin(), b.end());int t = 0;for (int i = 0; i < a.size() || i < b.size(); i++) {if (i < a.size()) t += to_int(a[i]);if (i < b.size()) t += to_int(b[i]);res += to_char(t % k);t /= k;}if (t) res += '1';reverse(res.begin(), d());cout << res << endl;
}

时空复杂度 O ( max ⁡ { l A , l B } ) O(max{l_A,l_B}) O(max{lA​,lB​})， l A , l B l_A,l_B lA​,lB​分别表示两个数的位数。