蓝桥杯 adv197 P1001

蓝桥杯 adv197 P1001

问题描述

当两个比较大的整数相乘时,可能会出现数据溢出的情形。为避免溢出,剋采用字符串的方法来实现两个大数之间的乘法。

具体来说,首先以字符串的形式输入两个整数,每个整数的长度不会超过8位,然后把它们相乘的结果存储在另一个字符串当中(长度不会超过16位),最后把这个字符串打印出来。例如,假设用户输入为:62773417 和 12345678,则输出结果为:774980393241726

输入

62773417 12345678

输出

774980393241726

参考解答

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
#include <iostream>
#include <string>

using namespace std;

string count_add(string s1, string s2) {
// 两个字符串相加
int len1 = s1.length();
int len2 = s2.length();

if (len1 > len2) {
return count_add(s2, s1);
}

for (int i = len1 - 1, j = len2 - 1; i >= 0; --i, --j) {
s2[j] += s1[i] - '0';

if (s2[j] > '9') {
s2[j] -= 10;

if (j == 0) {
s2 = "1" + s2;
} else {
++s2[j - 1];
}
}
}

return s2;
}

int main() {
string s1, s2;
cin >> s1 >> s2;

bool nega_s1 = false, nega_s2 = false; // 记录正负号

if (s1[0] == '-') {
nega_s1 = true; // 记录符号
s1.substr(1); // 取出数字部分
}

if (s2[0] == '-') {
nega_s2 = true;
s2.substr(1);
}

int a, b, tmp;
int len1 = s1.length(), len2 = s2.length();
char unit, decade = '0';
string tmp_res[s2.length()];

for (int i = len2 - 1; i >= 0; --i) {
a = s2[i] - '0';
for (int j = len1 - 1; j >= 0; --j) {
b = s1[j] - '0';
tmp = a * b + decade - '0';
unit = tmp % 10 + '0';
decade = tmp / 10 + '0';

tmp_res[len2 - 1 - i] = unit + tmp_res[len2 - 1 - i];
}

if (decade != '0') {
tmp_res[len2 - 1 - i] = decade + tmp_res[len2 - 1 - i];
}

decade = '0';
}

for (int i = 0; i < len2; ++i) {
for (int j = i; j > 0; j--)
tmp_res[i] = tmp_res[i] + '0';
}

string res = "0";
int st = 0; // 记录 非 0 的起始位置

for (int i = 0 ; i < len2; ++i)
res = count_add(res, tmp_res[i]);

for (int i = 0; i < res.size(); ++i) {
if (res[i] != '0') {
break;
}
++st;
}

res = res.substr(st);

if (nega_s1 + nega_s1 == 1)
cout << "-";
cout << res;
return 0;
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×