Hướng dẫn giải của TIN10_BEGIN05: Tổng và tích bigNum
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho hai số nguyên A và B rất lớn (|A|, |B| không quá 10^99), in tổng trên dòng 1 và tích trên dòng 2.
Cách làm
Các số quá lớn nên không lưu được trong long long. Ta đọc chúng dưới dạng chuỗi kí tự, rồi làm phép cộng, trừ, nhân giống như làm bằng tay.
Các bước chính:
- Tách dấu âm: nếu chuỗi bắt đầu bằng '-' thì ghi nhớ số đó âm và bỏ dấu đi. Sau đó bỏ các số 0 ở đầu.
- Tổng: nếu hai số cùng dấu thì cộng độ lớn, giữ dấu chung. Nếu khác dấu thì trừ số nhỏ hơn cho số lớn hơn về độ lớn, lấy dấu của số có độ lớn lớn hơn.
- Tích: nhân từng cặp chữ số rồi cộng vào đúng vị trí, sau đó chuyển nhớ từ phải sang trái. Tích âm khi hai số khác dấu.
- Nếu kết quả bằng 0 thì không in dấu '-'.
Bẫy cần nhớ: đừng in ra "-0", và bỏ các số 0 thừa ở đầu kết quả.
#include <bits/stdc++.h>
using namespace std;
// Bo cac chu so 0 o dau. Neu het chu so thi tra ve "0"
string boSo0(string s) {
int i = 0;
while (i < (int)s.size() - 1 && s[i] == '0') {
i++;
}
return s.substr(i);
}
// So sanh hai so khong am dang chuoi: tra ve true neu a >= b
bool lonHonHoacBang(string a, string b) {
if (a.size() != b.size()) {
return a.size() > b.size();
}
return a >= b;
}
// Cong hai so khong am dang chuoi (cong tung cap chu so, nho sang trai)
string cong(string a, string b) {
string kq = "";
int nho = 0;
int i = a.size() - 1;
int j = b.size() - 1;
while (i >= 0 || j >= 0 || nho > 0) {
int tong = nho;
if (i >= 0) {
tong += a[i] - '0';
i--;
}
if (j >= 0) {
tong += b[j] - '0';
j--;
}
kq += (char)('0' + tong % 10);
nho = tong / 10;
}
reverse(kq.begin(), kq.end());
return kq;
}
// Tru hai so khong am dang chuoi, yeu cau a >= b
string tru(string a, string b) {
string kq = "";
int muon = 0;
int i = a.size() - 1;
int j = b.size() - 1;
while (i >= 0) {
int hieu = (a[i] - '0') - muon;
muon = 0;
if (j >= 0) {
hieu -= (b[j] - '0');
j--;
}
if (hieu < 0) {
hieu += 10;
muon = 1;
}
kq += (char)('0' + hieu);
i--;
}
reverse(kq.begin(), kq.end());
return boSo0(kq);
}
// Nhan hai so khong am dang chuoi theo cach nhan tung cap chu so
string nhan(string a, string b) {
int na = a.size();
int nb = b.size();
int c[500];
for (int k = 0; k < na + nb; k++) {
c[k] = 0;
}
for (int i = 0; i < na; i++) {
for (int j = 0; j < nb; j++) {
c[i + j + 1] += (a[i] - '0') * (b[j] - '0');
}
}
// Chuyen nho tu phai sang trai
for (int k = na + nb - 1; k >= 1; k--) {
c[k - 1] += c[k] / 10;
c[k] = c[k] % 10;
}
string kq = "";
for (int k = 0; k < na + nb; k++) {
kq += (char)('0' + c[k]);
}
return boSo0(kq);
}
int main() {
string A, B;
cin >> A >> B;
// Tach dau am va phan do lon
bool amA = (A[0] == '-');
bool amB = (B[0] == '-');
string a = A;
string b = B;
if (amA) {
a = A.substr(1);
}
if (amB) {
b = B.substr(1);
}
a = boSo0(a);
b = boSo0(b);
// Tinh tong (dau cua tong phu thuoc vao so lon hon)
string tongDoLon;
bool tongAm;
if (amA == amB) {
tongDoLon = cong(a, b);
tongAm = amA;
} else if (lonHonHoacBang(a, b)) {
tongDoLon = tru(a, b);
tongAm = amA;
} else {
tongDoLon = tru(b, a);
tongAm = amB;
}
if (tongDoLon == "0") {
tongAm = false;
}
// Tinh tich: am khi hai so khac dau
string tichDoLon = nhan(a, b);
bool tichAm = (amA != amB);
if (tichDoLon == "0") {
tichAm = false;
}
if (tongAm) {
cout << "-";
}
cout << tongDoLon << "\n";
if (tichAm) {
cout << "-";
}
cout << tichDoLon << "\n";
return 0;
}
Bình luận