Hướng dẫn giải của Nhân 2 số nguyên lớn
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhậpTác giả: , , ,
Hiểu bài toán
Cho hai số nguyên không âm lớn a và b, mỗi số có độ dài lên đến 1000 chữ số. Nhiệm vụ là tính tích a × b. Vì các số này quá lớn để lưu trữ trong các kiểu dữ liệu nguyên chuẩn (như long long), chúng ta phải xử lý chúng như các chuỗi ký tự hoặc sử dụng mảng các chữ số. Việc nhân hai số lớn thường được thực hiện bằng cách mô phỏng lại cách nhân từng cột như cách chúng ta làm trên giấy.
Các cách tiếp cận
Cách Mô phỏng nhân từng cột (Grade School Algorithm)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void reverse_string(char *str) {
int len = strlen(str);
int i = 0, j = len - 1;
char temp;
while (i < j) {
temp = str[i];
str[i] = str[j];
str[j] = temp;
i++;
j--;
}
}
int main() {
char a_str[1002];
char b_str[1002];
scanf("%s", a_str);
scanf("%s", b_str);
if (strcmp(a_str, "0") == 0 || strcmp(b_str, "0") == 0) {
printf("0\n");
return 0;
}
int len_a = strlen(a_str);
int len_b = strlen(b_str);
// Mảng kết quả. Kích thước tối đa là len_a + len_b
int *result = (int*)calloc(len_a + len_b + 2, sizeof(int));
// Đảo ngược chuỗi để thực hiện phép nhân từ chữ số cuối (units) đến đầu
reverse_string(a_str);
reverse_string(b_str);
// Nhân từng chữ số và cộng vào vị trí tương ứng
for (int i = 0; i < len_a; i++) {
for (int j = 0; j < len_b; j++) {
int digit_a = a_str[i] - '0';
int digit_b = b_str[j] - '0';
result[i + j] += digit_a * digit_b;
}
}
// Xử lý số nhớ
int carry = 0;
for (int i = 0; i < len_a + len_b; i++) {
int sum = result[i] + carry;
result[i] = sum % 10;
carry = sum / 10;
}
// Tìm độ dài thực tế của kết quả (loại bỏ số 0 ở đầu)
int res_len = len_a + len_b;
while (res_len > 0 && result[res_len - 1] == 0) {
res_len--;
}
// In kết quả (đảo ngược lại)
for (int i = res_len - 1; i >= 0; i--) {
printf("%d", result[i]);
}
printf("\n");
free(result);
return 0;
}
- Time Complexity: O(N * M)
- Space Complexity: O(N + M)
Phương pháp này mô phỏng chính xác cách nhân trên giấy. Đầu tiên, chúng ta đảo ngược hai chuỗi đầu vào để xử lý dễ dàng hơn (luôn xử lý từ chỉ số 0). Sau đó, ta dùng hai vòng lặp lồng nhau để nhân từng chữ số của a với từng chữ số của b. Kết quả của phép nhân a[i] * b[j] sẽ được cộng vào vị trí i + j trong mảng kết quả. Sau khi nhân xong, ta duyệt qua mảng kết quả để xử lý các giá trị lớn hơn 10 (số nhớ), chuyển phần dư và cộng số nhớ vào cột tiếp theo. Cuối cùng, ta in ngược lại kết quả từ vị trí cao nhất còn khác 0.
Cách Thuật toán Karatsuba (Tối ưu hơn)
// Đây là pseudo-code minh họa logic Karatsuba
// Để implement đầy đủ cần các hàm cộng/trừ/nhân chuỗi hỗ trợ
#include <stdio.h>
#include <string.h>
// Hàm cộng hai chuỗi số lớn
char* add(char* a, char* b);
// Hàm trừ hai chuỗi số lớn
char* sub(char* a, char* b);
// Hàm nhân hai chuỗi số lớn (dùng cho các phần nhỏ hơn)
char* multiply(char* a, char* b);
char* karatsuba(char* x, char* y) {
int n = strlen(x);
int m = strlen(y);
// Cơ sở: nếu số nhỏ, dùng phép nhân thường O(1)
if (n < 10 || m < 10) {
// Chuyển sang số nguyên, nhân, rồi chuyển về chuỗi
// ... code chuyển đổi ...
return result;
}
int half = (n > m ? n : m) / 2;
// Chia a và b thành 2 phần
// ... code chia chuỗi ...
char *high1, *low1, *high2, *low2;
// z0 = low1 * low2
char *z0 = karatsuba(low1, low2);
// z2 = high1 * high2
char *z2 = karatsuba(high1, high2);
// z1 = (high1 + low1) * (high2 + low2) - z2 - z0
char *sum1 = add(high1, low1);
char *sum2 = add(high2, low2);
char *z1 = multiply(sum1, sum2);
z1 = sub(z1, z2);
z1 = sub(z1, z0);
// Kết quả = z2 * 10^(2m) + z1 * 10^m + z0
// ... code dịch trái (thêm số 0) và cộng ...
return result;
}
- Time Complexity: O(N^1.58)
- Space Complexity: O(N)
Karatsuba là một thuật toán nhân nhanh, sử dụng phương pháp chia để trị (Divide and Conquer). Thay vì thực hiện 4 phép nhân cho hai số có n chữ số (như thuật toán grade school), Karatsuba chỉ cần 3 phép nhân cho các phần halves. Cụ thể, tính z0, z1, z2 theo công thức: Z = z2 * 10^(2m) + z1 * 10^m + z0. Phương pháp này giảm đáng kể số lượng phép nhân với độ phức tạp O(N^log2(3)) ≈ O(N^1.58), hiệu quả hơn nhiều so với O(N^2) khi N lớn. Tuy nhiên, code cài đặt phức tạp hơn nhiều vì phải xử lý chuỗi con, cộng trừ chuỗi và quản lý bộ nhớ.
Cách Sử dụng thư viện (BigInt)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
// Trong C++, các ngôn ngữ hiện đại khác (Java, Python) có hỗ trợ sẵn BigInt.
// Nếu làm thủ công trong C++, ta có thể dùng struct hoặc class.
// Đây là ví dụ về cách dùng algorithm base 10000 hoặc 10^9 để tối ưu.
const int BASE = 1000000000;
struct BigInt {
vector<long long> digits;
bool is_neg;
BigInt(string s = "0") {
if (s[0] == '-') { is_neg = true; s = s.substr(1); }
else is_neg = false;
for (int i = s.length(); i > 0; i -= 9) {
if (i < 9)
digits.push_back(stoll(s.substr(0, i)));
else
digits.push_back(stoll(s.substr(i - 9, 9)));
}
trim();
}
void trim() {
while (digits.size() > 1 && digits.back() == 0) {
digits.pop_back();
}
if (digits.size() == 1 && digits[0] == 0) is_neg = false;
}
// ... Các toán tử cộng, trừ ...
BigInt operator*(const BigInt& other) const {
// Implement O(N^2) multiplication
BigInt res;
res.digits.resize(digits.size() + other.digits.size(), 0);
for (size_t i = 0; i < digits.size(); i++) {
long long carry = 0;
for (size_t j = 0; j < other.digits.size() || carry; j++) {
long long cur = res.digits[i+j] + digits[i] * (j < other.digits.size() ? other.digits[j] : 0) + carry;
res.digits[i+j] = cur % BASE;
carry = cur / BASE;
}
}
res.is_neg = is_neg ^ other.is_neg;
res.trim();
return res;
}
};
int main() {
string s1, s2;
cin >> s1 >> s2;
BigInt a(s1), b(s2);
BigInt c = a * b;
if (c.digits.empty()) cout << 0;
else {
if (c.is_neg) cout << '-';
cout << c.digits.back();
for (int i = c.digits.size() - 2; i >= 0; i--) {
cout << setfill('0') << setw(9) << c.digits[i];
}
}
cout << endl;
}
- Time Complexity: O(N^2 / log^2(BASE))
- Space Complexity: O(N)
Trong lập trình thi đấu, cách hiệu quả nhất thường là sử dụng các thư viện lớn hoặc viết một lớp BigInt. Tuy nhiên, do giới hạn của C (và đề bài chỉ yêu cầu C/C++), cách tiếp cận này mô phỏng việc sử dụng Base lớn (ví dụ: 10^9) để lưu trữ các nhóm chữ số. Thay vì lưu mỗi chữ số 10, ta lưu 9 chữ số trong một phần tử mảng kiểu long long. Điều này giảm độ dài mảng đi 9 lần và giảm số lần nhân lặp lại. Phép nhân vẫn là O(N^2) về mặt lý thuyết nhưng nhanh hơn đáng kể trong thực tế và tránh tràn số nhớ nếu dùng đúng kiểu.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N * M) | O(N + M) | Mô phỏng nhân từng cột (Grade School Algorithm) |
| 2 | O(N^1.58) | O(N) | Thuật toán Karatsuba (Tối ưu hơn) |
| 3 | O(N^2 / log^2(BASE)) | O(N) | Sử dụng thư viện (BigInt) |
Bài học kinh nghiệm
- Đảo ngược chuỗi số trước khi thực hiện phép nhân giúp việc lấy chỉ số và cộng số nhớ dễ dàng hơn (xử lý từ chữ số đơn vị lên hàng nghìn tỷ).
- Kiểu dữ liệu lưu trữ kết quả trung gian phải đủ lớn để chứa tổng số nhớ (ví dụ: mảng int thay vì char).
- Có thể tối ưu bằng cách dùng Base lớn (ví dụ 10^9) để giảm kích thước mảng và số lần nhân.
Lỗi thường gặp
- Quên xử lý trường hợp một trong hai số là 0 (đặc biệt nếu không có bước loại bỏ số 0 ở đầu).
- Xử lý số nhớ sai ở bước cuối cùng (bỏ qua số nhớ cuối cùng hoặc in thừa số 0).
- Tràn bộ nhớ nếu khai báo mảng quá nhỏ (mảng phải có kích thước ít nhất là tổng độ dài hai số).
- Lỗi quy đổi ký tự sang số (lấy sai giá trị ASCII).
Bình luận