Nhân số lớn biểu diễn bằng chuỗi trong C++

Cho hai số nguyên dương rất lớn dưới dạng chuỗi. Nhân chúng mà không dùng kiểu dữ liệu lớn (bigint).

Ý tưởng: mô phỏng nhân cột tay, dùng mảng lưu kết quả trung gian.

Ví dụ

"34" × "57" = "1938"

Thuật toán

• Tạo mảng product kích thước len1 + len2 khởi tạo 0.
• Duyệt ngược chuỗi 1 (i), chuỗi 2 (j):
  • mul = (num1[i]-'0') * (num2[j]-'0') + product[i+j+1]
  • product[i+j+1] = mul % 10
  • product[i+j] += mul / 10
• Chuyển mảng số thành chuỗi, bỏ số 0 đầu nếu có.

Triển khai C++

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

string multiplyStrings(string num1, string num2) {
    if (num1 == "0" || num2 == "0") return "0";
    int n = num1.size(), m = num2.size();
    vector prod(n + m, 0);

    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            int mul = (num1[i] - '0') * (num2[j] - '0') + prod[i + j + 1];
            prod[i + j + 1] = mul % 10;
            prod[i + j] += mul / 10;
        }
    }

    string res;
    for (int d : prod) {
        if (!(res.empty() && d == 0)) res.push_back('0' + d);
    }
    return res.empty() ? "0" : res;
}

int main() {
    string a = "34", b = "57";
    cout << multiplyStrings(a, b) << endl; // 1938
    return 0;
}

Kết quả

1938