Xử Lý Số Nguyên Lớn

1. Bản chất vấn đề & trực giác thuật toán (the core problem & intuition)

Trong ngôn ngữ lập trình C++, kiểu dữ liệu số nguyên có kích thước lớn nhất được hỗ trợ phần cứng là unsigned long long (64-bit, tối đa xấp xỉ $1.84 \times 10^{19}$) hoặc phần mở rộng GCC __int128 (128-bit, tối đa xấp xỉ $3.4 \times 10^{38}$).

Tuy nhiên, trong các bài toán thực tế và đề thi học sinh giỏi (như tính $100!$, tính số Fibonacci thứ $1000$, hoặc tính $2^{10000}$ mà không lấy dư modulo), kết quả có thể dài hàng nghìn đến hàng chục nghìn chữ số. Vì C++ không có sẵn kiểu dữ liệu BigInteger như Python hay Java, lập trình viên thi đấu C++ bắt buộc phải tự mô phỏng các phép tính số học đặt tính rồi tính như toán tiểu học trên mảng ký tự (string) hoặc mảng số nguyên (vector<int>).

Big integer hay modular arithmetic: Chọn vũ khí nào?

2. Mô phỏng từng bước (visual step-by-step simulation)

Ví dụ 1: Mô phỏng phép cộng số lớn $A = 9876$ và $B = 543$

• Quy tắc: Đảo ngược chuỗi để chữ số hàng đơn vị nằm ở chỉ số 0.
• $A' = [6, 7, 8, 9]$, $B' = [3, 4, 5]$.

• Kết quả đảo ngược: $[9, 1, 4, 0, 1] \implies \mathbf{10419}$.

Ví dụ 2: Mô phỏng phép nhân số lớn $A = 48$ với số nhỏ $b = 7$

• $A' = [8, 4]$.
• Bước 0 ($i = 0$): $8 \times 7 + 0 = 56 \implies$ Ghi $6$, carry $= 5$.
• Bước 1 ($i = 1$): $4 \times 7 + 5 = 33 \implies$ Ghi $3$, carry $= 3$.
• Dư cuối: Ghi carry $= 3$.
• Kết quả đảo ngược: $[6, 3, 3] \implies \mathbf{336}$.

3. Lý thuyết cốt lõi & bất biến thuật toán (core invariants)

3.1. Mô hình biểu diễn số lớn & little-endian

• Biểu diễn Little-Endian: Lưu các chữ số theo thứ tự từ hàng thấp đến hàng cao (chữ số hàng đơn vị nằm ở chỉ số 0).
• Ưu điểm cốt lõi: Hàng đơn vị nằm ở index = 0, nên khi cộng, trừ hoặc nhân ta có thể xử lý trực tiếp từ hàng thấp lên hàng cao và truyền biến nhớ carry/borrow sang phần tử kế tiếp ($a[0] \to a[1] \to a[2] \dots$). Ngoài ra, chữ số mới ở cuối có thể được thêm bằng push_back() với chi phí amortized $\mathcal{O}(1)$.
• Biểu diễn Base 10 vs Base $10^9$:
• Base 10 (string / vector<int>): Mỗi phần tử lưu 1 chữ số thập phân ($0 \dots 9$).
• Base $10^9$ (vector<int> / vector<long long>): Nhóm các cụm 9 chữ số từ phải sang trái.
• Cấu trúc dữ liệu: Mỗi chunk lưu kiểu int ($0 \dots 999,999,999$); phép nhân giữa 2 chunks lưu kiểu long long (vì $(10^9 - 1) \times (10^9 - 1) \approx 10^{18} < 2^{63}-1$).
• Ví dụ: Số $1234567890123456789$ được tách thành: $$\text{chunks} = [23456789, 123456789, 1]$$ $$\text{Giá trị} = 23456789 + 123456789 \times 10^9 + 1 \times (10^9)^2$$

3.2. Bảng tổng hợp các phép toán số nguyên lớn ($\mathcal{O}(L^2)$)

3.3. Thuật toán chia số lớn cho số nhỏ & bất biến horner

Khi chia số lớn $A$ cho số nguyên $b$ ($1 \le b \le 10^9$), ta duyệt từ chữ số hàng cao nhất xuống hàng đơn vị:

string divSmall(string a, long long b) {
    string res = "";
    long long cur = 0;
    for (char c : a) {
        cur = cur * 10 + (c - '0');
        int digit = cur / b;
        res.push_back(char('0' + digit));
        cur %= b; // cur luôn là số dư hiện tại
    }
    // Xóa số 0 vô nghĩa ở đầu
    int pos = 0;
    while (pos + 1 < (int)res.size() && res[pos] == '0') pos++;
    return res.substr(pos);
}

Ghi chú:

BẤT BIẾN TOÁN HỌC CỦA PHÉP CHIA TỪNG BƯỚC:

Vì trước mỗi bước lặp ta luôn duy trì số dư $0 \le cur < b$, nên sau khi nhận thêm một chữ số mới $cur = cur \times 10 + \text{digit}$, giá trị luôn thỏa mãn $cur < 10b$. Do đó thương tại mỗi bước digit = cur / b chắc chắn luôn nằm trong khoảng $[0, 9]$ (là một chữ số thập phân hợp lệ duy nhất).

3.4. Tối ưu hóa base $10^9$ (chunking optimization)

• Thay vì thực hiện phép nhân trên từng chữ số đơn lẻ (Base 10 có $L$ chữ số), ta nén số lớn thành $\frac{L}{9}$ chunks trong Base $10^9$.
• Đánh giá hiệu năng: Số lượng cặp chunk cần nhân giảm xấp xỉ $\left(\frac{L}{9}\right) \times \left(\frac{L}{9}\right) = \frac{L^2}{81}$ (giảm khoảng 81 lần về số lượng phép nhân chunk). Tốc độ thực tế tăng vọt từ hàng chục lần giúp vượt qua các bài toán $N \le 10^5$.

4. Các bẫy lỗi lập trình kinh điển (bug traps)

1. Quên xóa số 0 vô nghĩa ở đầu (Leading Zeros): * Sau phép trừ (ví dụ $1000 - 999 = 0001$), nếu không xóa số 0 thì chuỗi sẽ in ra 0001. * Cách xử lý: while (res.size() > 1 && res.back() == '0') res.pop_back();.

2. Không xét trường hợp số $0$: * Phép nhân $A \times 0$ phải trả về "0", không được trả về rỗng "".

3. Biến carry trong phép nhân số nhỏ có thể rất lớn: * Trong phép nhân $A \times b$ với $b = 10^9$, carry sau mỗi bước có thể lên tới $10^9$, do đó kiểu dữ liệu của carry bắt buộc phải là long long.

5. Mẫu cài đặt chuẩn thi đấu (competitive templates)

# include <bits/stdc++.h>
using namespace std;

// Hàm xóa số 0 vô nghĩa ở đầu chuỗi đảo ngược
void removeLeadingZeros(string &s) {
    while (s.size() > 1 && s.back() == '0') {

        s.pop_back();
    }
}

// Phép cộng 2 số nguyên lớn không âm (A + B)
string addBig(string a, string b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    string res = "";
    int carry = 0;
    int n = max(a.size(), b.size());

    for (int i = 0; i < n || carry; ++i) {
        int sum = carry;
        if (i < (int)a.size()) sum += a[i] - '0';
        if (i < (int)b.size()) sum += b[i] - '0';
        res.push_back((sum % 10) + '0');
        carry = sum / 10;
    }

    reverse(res.begin(), res.end());
    return res;
}

// Phép trừ 2 số nguyên lớn không âm (A - B với A >= B)
string subBig(string a, string b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    string res = "";
    int borrow = 0;

    for (int i = 0; i < (int)a.size(); ++i) {
        int diff = (a[i] - '0') - borrow;
        if (i < (int)b.size()) diff -= (b[i] - '0');
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        res.push_back(diff + '0');
    }

    removeLeadingZeros(res);
    reverse(res.begin(), res.end());
    return res;
}

// Phép nhân 2 số nguyên lớn chuẩn mực và an toàn (A * B)
string mulBig(string a, string b) {
    if (a == "0" || b == "0") return "0";

    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    int n = a.size(), m = b.size();
    vector<int> c(n + m, 0);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            c[i + j] += (a[i] - '0') * (b[j] - '0');
        }
    }

    // Normalize: Đẩy biến nhớ carry sang các ô kế tiếp
    for (int i = 0; i + 1 < n + m; ++i) {
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }

    while (c.size() > 1 && c.back() == 0) {

        c.pop_back();
    }

    string res = "";
    for (int i = (int)c.size() - 1; i >= 0; --i) {
        res.push_back(c[i] + '0');
    }

    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string a, b;
    if (!(cin >> a >> b)) return 0;

    cout << "A + B = " << addBig(a, b) << "\n";
    cout << "A * B = " << mulBig(a, b) << "\n";
    return 0;
}