Hướng dẫn giải của Nhân 2 số nguyên lớn


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.

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ập

Tác giả: Hiếu Nguyễn, TVC2309, lehongxn4gmail, nquang2909

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

Please read the guidelines before commenting.


Không có bình luận tại thời điểm này.