Chia số lớn biểu diễn dưới dạng chuỗi trong C++

Giới thiệu

Thực hiện phép chia số lớn (nhiều chữ số, vượt quá giới hạn kiểu dữ liệu) cho một số nguyên nhỏ, sử dụng thuật toán chia tay (long division) trên chuỗi ký tự.

Thuật toán chia tay

Mô phỏng quy trình chia viết tay:

1. Lấy lần lượt các chữ số từ trái sang phải
2. Ghép thành số tạm thời (dividend) đủ lớn để chia cho divisor
3. Thực hiện chia, lấy thương ghi vào kết quả
4. Lấy dư, ghép với chữ số tiếp theo, tiếp tục

Ví dụ: 12345678901234567890 ÷ 75

Bước 1: Lấy 1 → 1 < 75, lấy thêm → 12 < 75, lấy thêm → 123 ≥ 75
Bước 2: 123 ÷ 75 = 1 dư 48 → Kết quả: "1"
Bước 3: Dư 48 ghép 4 → 484 ÷ 75 = 6 dư 34 → Kết quả: "16"
Bước 4: Dư 34 ghép 5 → 345 ÷ 75 = 4 dư 45 → Kết quả: "164"
... tiếp tục ...

Mã nguồn hoàn chỉnh

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

string divideLargeNumber(string number, int divisor) {
    string result;
    int index = 0;
    int len = number.length();
    
    // Tìm phần đầu đủ lớn để chia
    int dividend = number[index] - '0';
    while (index < len && dividend < divisor) {
        index++;
        if (index < len) {
            dividend = dividend * 10 + (number[index] - '0');
        }
    }
    
    // Nếu toàn bộ số nhỏ hơn divisor
    if (dividend < divisor) {
        return "0";
    }
    
    // Thực hiện chia
    while (index < len) {
        result += char(dividend / divisor + '0');
        dividend = (dividend % divisor) * 10 + (number[++index] - '0');
    }
    
    // Xử lý trường hợp kết quả rỗng
    if (result.empty()) return "0";
    
    return result;
}

int main() {
    string large_number = "12345678901234567890";
    int divisor = 75;
    cout << divideLargeNumber(large_number, divisor) << endl;
    return 0;
}

Kết quả chạy chương trình

164609052016460905

Phân tích độ phức tạp

• Thời gian: O(n) - n là độ dài chuỗi số lớn
• Không gian: O(n) - lưu chuỗi kết quả

Mở rộng: Trả về cả thương và dư

pair<string, int> divideWithRemainder(string number, int divisor) {
    string quotient;
    int remainder = 0;
    int index = 0;
    int len = number.length();
    
    while (index < len) {
        remainder = remainder * 10 + (number[index] - '0');
        int q = remainder / divisor;
        if (!quotient.empty() || q != 0 || index == len - 1) {
            quotient += char(q + '0');
        }
        remainder = remainder % divisor;
        index++;
    }
    
    if (quotient.empty()) quotient = "0";
    return {quotient, remainder};
}

Ứng dụng thực tế

• Xử lý số lớn trong mật mã học (RSA, ECC)
• Tính toán tài chính chính xác (số tiền lớn)
• Khoa học máy tính, mô phỏng vật lý

Kết luận

Thuật toán chia số lớn dạng chuỗi là kỹ năng cơ bản trong lập trình thi đấu và xử lý big integer. C++ không có big integer built-in như Python/Java, nên việc tự triển khai rất quan trọng.