Xử lý số nguyên lớn (phần 2) - Các phép toán Nhân

    Đây là phần 2 của series bài viết về Xử lý số nguyên lớn trong C++. Trước khi đọc bài này, các bạn cần biết cách biểu diễn số nguyên lớn, cũng như các phép toán so sánh, cộng, trừ số lớn. Nếu như chưa nắm vững, các bạn hãy tìm đọc lại tại đây.

    Trong bài viết có sử dụng lại một số khái niệm của bài viết trước, người viết xin phép thống kê ra trước tại đây để bạn đọc dễ dàng hiểu được các đoạn code hơn:

  • Kiểu dữ liệu chuỗi kí tự biểu diễn số lớn: typedef string bignum_str;.
  • Kiểu dữ liệu mảng lưu chữ số biểu diễn số lớn: typedef vector < int > vi;.

    Bây giờ, chúng ta sẽ bắt đầu đến với các phép toán Nhân trên tập số lớn!

I. Các phép toán Nhân

1. Nhân một số lớn với một số nhỏ

    Số nhỏ ở đây ta hiểu là số có thể biểu diễn được bằng các kiểu dữ liệu nguyên thủy. Với một phép nhân số lớn aa cho số nhỏ b,b, ta có thể sử dụng phương pháp bằng chuỗi kí tự vì phương pháp bằng mảng cài đặt sẽ rất phức tạp Lưu ý rằng bb ở đây sẽ ràng buộc không vượt quá 101810^{18}. Trường hợp bb lớn hơn nữa nhưng vẫn là số nhỏ (chẳng hạn như b=2641b = 2^{64} - 1), thì thuật toán này sẽ có khả năng cao xảy ra tràn số. Khi đó ta cần chuyển bb sang kiểu số lớn và thực hiện thuật toán nhân hai số lớn thì mới an toàn.

    Phương pháp sử dụng chuỗi như sau:

  • Bước 1: Duyệt từ cuối chuỗi số lớn về đầu, lấy tích từng kí tự số của số lớn với số nhỏ, cộng thêm biến nhớ.
  • Bước 2: Điền chữ số cuối của kết quả bước 11 vào bên trái của kết quả cuối. Tuy nhiên, nếu như làm vậy với chuỗi kí tự thì độ phức tạp sẽ khá lớn, do vậy ta sẽ vẫn thêm chữ số vào cuối chuỗi kết quả, rồi cuối cùng sẽ đảo ngược chuỗi kết quả lại.
  • Bước 3: Gán biến nhớ bằng phần nguyên của kết quả ở bước 1 chia cho 1010.

Cài đặt 1: Nhân một số lớn với một số nhỏ bằng chuỗi kí tự

bignum_str product(bignum_str a, long long b)
{
    int carry = 0;
    bignum_str res;
    for (int i = a.size() - 1; i >= 0; --i)
    {
        // Lấy tích chữ số và số nhỏ, cộng thêm biến nhớ từ hàng bên phải.
        long long s = (a[i] - '0') * b + carry; 
        carry = s / 10; // Giá trị nhớ đẩy sang hàng bên trái.
        res += (char) (s % 10 + '0'); 
    }
    
    // Nếu vẫn còn nhớ thì viết nốt nó sang bên trái kết quả.
    if (carry > 0)
        while (carry != 0)
        {
            res += (char) (carry % 10 + '0');
            carry /= 10;
        }

    // Đảo ngược chuỗi kết quả để thu được kết quả đúng.
    reverse(res.begin(), res.end());
	
    return res;
}

    Độ phức tạp của phương pháp là O(n),O(n), với nn là độ dài của số lớn. Tuy nhiên, tác giả vẫn khuyên các bạn nên chuyển số nhỏ sang số lớn rồi thực hiện thuật toán nhân hai số lớn bên dưới!

2. Phép nhân hai số lớn

    Đối với phép nhân hai số lớn, phương pháp sử dụng chuỗi sẽ không phù hợp vì thời gian chạy rất lâu và xử lý khó khăn. Do đó tôi sẽ chỉ giới thiệu phương pháp sử dụng mảng. Thuật toán như sau:

  • Bước 1: Ta đảo ngược các chữ số của hai số lớn để dễ tính toán. Giả sử đó là hai số aab,b, đều lưu ở kiểu vi.
  • Bước 2: Tạo một mảng cc để lưu kết quả phép nhân. Gọi số lượng chữ số của aabb lần lượt là mmnn thì ta có nhận xét rằng kết quả của phép nhân a×ba \times b sẽ luôn có số lượng chữ số không vượt quá m+n+1,m + n + 1, nên ta khởi tạo mảng cc với kích thước tương tự.
  • Bước 3: Duyệt qua các cặp chữ số ai,bj (0i<m,0j<n),a_i, b_j \ (0 \le i < m, 0 \le j < n), cộng thêm kết quả ai×bja_i \times b_j vào vị trí ci+jc_{i + j}. Để tránh tràn số, ta sẽ đẩy luôn phần nhớ là ci+j10\left\lfloor{\frac{c_{i + j}}{10}}\right\rfloor sang vị trí ci+j+1,c_{i + j + 1}, và chỉ giữ lại giá trị ci+j mod 10c_{i + j} \text{ mod } 10 ở vị trí ci+jc_{i + j}.
  • Bước 4: Xử lý nốt các vị trí còn lớn hơn 10,10, đẩy giá trị nhớ sang hàng đằng trước và cuối cùng xóa các chữ số 00 vô nghĩa ở đầu kết quả đi (do kĩ thuật code nên cần phải xóa chữ số 00 vô nghĩa).

    Cài đặt: Nhân hai số lớn bằng mảng lưu chữ số:

// Xóa các số 0 vô nghĩa ở đầu.
void del_zero(vi &a) 
{ 
    reverse(a.begin(), a.end()); 
	
    while (a.size() >= 2) 
        if (a.back() == 0) 
            a.pop_back();
        else 
            break;

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

// Nhân hai số lớn.
vi operator * (vi a, vi b)
{
    // Đảo ngược hai số trước để tiện tính toán.
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
	
    // Resize trước mảng kết quả. Kết quả của tích có thể đạt tới số chữ số  
    // bằng tổng độ dài của hai số ban đầu cộng lại và cộng thêm 1.
    vi c(a.size() + b.size() + 1);
    for (int i = 0; i < (int) a.size(); ++i)
        for (int j = 0; j < (int) b.size(); ++j)
        {
            c[i + j] += (a[i] * b[j]);
            c[i + j + 1] += (c[i + j] / 10);
            c[i + j] %= 10;
        }

    // Xử lý nốt phần giá trị nhớ chưa được cộng hết.
    // Mảng c hiện tại đang là mảng kết quả bị đảo ngược.
    c.push_back(0);
    for (int i = 0; i < (int) c.size() - 1; ++i) 
    {
    	c[i + 1] += (c[i] / 10);
    	c[i] %= 10;
    }

    // Đảo ngược mảng c và xóa các chữ số 0 vô nghĩa ở đầu, ta sẽ thu được tích a * b.
    reverse(c.begin(), c.end());
    del_zero(c);
	
    return c;
}

    Độ phức tạp của thuật toán này là O(n×m),O(n \times m), với nnmm lần lượt là độ dài của hai số cần nhân.

3. Chương trình đầy đủ

    Dưới đây là chương trình gồm đầy đủ các thao tác nhân với số nguyên lớn (chỉ sử dụng mảng lưu chữ số, vì cách làm này tối ưu hơn), bao gồm cả test lại các phép toán này. Bạn đọc có thể tham khảo để có cái nhìn tổng quan hơn về các thao tác này:

#include <bits/stdc++.h>

using namespace std;

typedef vector < int > vi;

// Nạp chồng toán tử nhập luồng, dùng để nhập vào số lớn.
istream &operator >> (istream &cin, vi &a)
{
    string s;
    cin >> s;

    a.clear();
    for (int i = 0; i < s.size(); ++i)
        a.push_back(s[i] - '0');

    return cin;
}

// Nạp chồng toán tử trích luồng, dùng để in ra số lớn.
ostream &operator << (ostream &cout, const vi &a) 
{
    for (auto d: a) 
        cout << d;

    return cout;
} 

// Xóa các số 0 vô nghĩa ở đầu.
void del_zero(vi &a) 
{ 
    reverse(a.begin(), a.end()); 
	
    while (a.size() >= 2) 
        if (a.back() == 0) 
            a.pop_back();
        else 
            break;

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

vi int_to_vi(int n)
{
    vi res;
    if (n == 0)
    {
        res.push_back(n);
        return res;
    }

    while (n)
    {
        res.push_back(n % 10);
        n /= 10;
    }

    return res;
}

// Nhân hai số lớn.
vi operator * (vi a, vi b)
{
    // Đảo ngược hai số trước để tiện tính toán.
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
	
    // Resize trước mảng kết quả. Kết quả của tích có thể đạt tới số chữ số  
    // bằng tổng độ dài của hai số ban đầu cộng lại và cộng thêm 1.
    vi c(a.size() + b.size() + 1);
    for (int i = 0; i < (int) a.size(); ++i)
        for (int j = 0; j < (int) b.size(); ++j)
        {
            c[i + j] += (a[i] * b[j]);
            c[i + j + 1] += (c[i + j] / 10);
            c[i + j] %= 10;
        }

    // Xử lý nốt phần giá trị nhớ chưa được cộng hết.
    // Mảng c hiện tại đang là mảng kết quả bị đảo ngược.
    c.push_back(0);
    for (int i = 0; i < (int) c.size() - 1; ++i) 
    {
    	c[i + 1] += (c[i] / 10);
    	c[i] %= 10;
    }

    // Đảo ngược mảng c và xóa các chữ số 0 vô nghĩa ở đầu, ta sẽ thu được tích a * b.
    reverse(c.begin(), c.end());
    del_zero(c);
	
    return c;
}

main()
{
    vi a, b;
    int n;
    
    cin >> a >> b;
    cin >> n;
	
    // Nhân số lớn a và số nhỏ n. Chuyển n qua số lớn để nhân.
    cout << a * int_to_vi(n) << '\n';
    // Nhân hai số lớn a và b.
    cout << a * b;
	
    return 0;
}

II. Bài toán minh họa

1. Số lượng hoán vị

Đề bài

    Cho trước số nguyên dương nn. Một hoán vị của các số từ 11 tới nn là một cách sắp xếp các số từ 11 tới nn theo thứ tự nào đó. Ví dụ, với n=3n = 3 ta có các hoán vị là: {1,2,3};{1,3,2};{2,1,3};{2,3,1};{3,1,2};{3,2,1}\{1, 2, 3\}; \{1, 3, 2\}; \{2, 1, 3\}; \{2, 3, 1\}; \{3, 1, 2\}; \{3, 2, 1\}.

    Yêu cầu: Hãy tính số lượng hoán vị của tập hợp gồm các số từ 11 tới n?n?

    Input:

  • Chứa duy nhất số nguyên dương nn.

    Ràng buộc:

  • 1n1061 \le n \le 10^6.

    Subtasks:

  • Subtask 11 (30%30\% số điểm): 1n501 \le n \le 50.
  • Subtask 22 (70%70\% số điểm): Không có ràng buộc gì thêm.

    Output:

  • In ra số lượng hoán vị của các số từ 11 tới nn.

    Sample Input:

3

    Sample Output:

6

Ý tưởng

    Theo công thức toán tổ hợp, số lượng hoán vị của một tập gồm nn thành phần sẽ là n!n!.

    Với subtask 11 thì việc tính toán có thể thực hiện bằng phép nhân thông thường mà không xảy ra tràn số.

    Tuy nhiên, với subtask số 2,2, bài toán tính n!n! với n106n \le 10^6 phải giải quyết bằng phép nhân số lớn. Thuật toán như sau: Ban đầu đặt một biến factorial\text{factorial} là kết quả cuối, khởi tạo giá trị 11 cho nó. Tiếp theo duyệt lần lượt các số ii từ 22 tới nn rồi nhân factorial\text{factorial} với giá trị ii sau khi chuyển qua số lớn. Toàn bộ các thao tác nhân sẽ là nhân hai số lớn.

    Độ phức tạp: O(n×α)O(n \times \alpha) với α\alpha là độ phức tạp của phép nhân hai số lớn.

Cài đặt

    Dưới đây tôi thử sử dụng phép nhân hai số lớn với phương pháp mảng lưu chữ số, toán tử * đã được nạp chồng ở phía trên. Ban đầu kết quả factorial\text{factorial} có giá trị là 1,1, nhưng vì nó là số lớn nên chúng ta cần viết thêm một hàm để chuyển nó qua số lớn kiểu vector trước.

    Ngoài ra, ta cũng lưu ý đến hàm nạp chồng toán tử chèn luồng, để in ra được một số lớn kiểu vi trực tiếp bằng hàm cout.

#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

typedef vector < int > vi;

// Nạp chồng toán tử chèn luồng, dùng để in ra số lớn.
ostream &operator << (ostream &cout, const vi &a)
{
    for (auto d: a)
        cout << d;

    return cout;
}

// Chuyển từ int sang vector < int >.
vi int_to_vi(int n) 
{ 
    vi c;
    if (n == 0) 
    {
        c.push_back(n);
        return c;
    }
	
    while (n) 
    {
        c.push_back(n % 10);
        n /= 10;
    }
	
    reverse(c.begin(), c.end());
	
    return c;
}

// Nhân hai số lớn.
vi operator * (vi a, vi b)
{
    // Đảo ngược hai số trước để tiện tính toán.
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
	
    // Resize trước mảng kết quả. Kết quả của tích có thể đạt tới số chữ số  
    // bằng tổng độ dài của hai số ban đầu cộng lại và cộng thêm 1.
    vi c(a.size() + b.size() + 1);
    for (int i = 0; i < (int) a.size(); ++i)
        for (int j = 0; j < (int) b.size(); ++j)
        {
            c[i + j] += (a[i] * b[j]);
            c[i + j + 1] += (c[i + j] / 10);
            c[i + j] %= 10;
        }

    // Xử lý nốt phần giá trị nhớ chưa được cộng hết.
    // Mảng c hiện tại đang là mảng kết quả bị đảo ngược.
    c.push_back(0);
    for (int i = 0; i < (int) c.size() - 1; ++i) 
    {
    	c[i + 1] += (c[i] / 10);
    	c[i] %= 10;
    }

    // Đảo ngược mảng c và xóa các chữ số 0 vô nghĩa ở đầu, ta sẽ thu được tích a * b.
    reverse(c.begin(), c.end());
    del_zero(c);
	
    return c;
}

vi calc_factorial(int n)
{
    vi factorial = int_to_vi(1);
    for (int i = 2; i <= n; ++i)
        factorial = factorial * int_to_vi(i);

    return factorial;
}

main()
{
    int n;
    cin >> n;
	
    cout << calc_factorial(n);
	
    return 0;
}

2. Tích lớn nhất

Đề bài

    Cho ba số nguyên a,b,ca,b,c và một số nguyên dương MM.

    Yêu cầu: Hãy tìm tích lớn nhất được tạo bởi hai trong ba số a,b,c?a,b,c?

    Ràng buộc:

  • a,b,c1018|a|,|b|,|c|≤10^{18}.

    Subtasks:

  • Subtask 11 (70%70\% số điểm): a,b,c109|a|, |b|, |c| \le 10^9.
  • Subtask 22 (30%30\% số điểm): Không có ràng buộc gì thêm.

Ý tưởng

    Với subtask 1,1, ta thực hiện tất cả các phép nhân hai cặp số và tìm ra kết quả.

    Với subtask 2,2, ta khéo léo nhận xét như sau để làm giảm số thao tác cần thực hiện:

  • Nếu có ít nhất hai số âm thì lấy tích hai số âm nhỏ nhất (lấy giá trị tuyệt đối của hai số đó nhân với nhau).
  • Nếu có ít nhất hai số không âm thì lấy tích hai số không âm lớn nhất.

    Tuy nhiên, trong subtask này ta sẽ cần cài đặt phép toán nhân hai số lớn và chuyển một số kiểu long long sang kiểu số lớn (do đề bài cho trước là các số nguyên).

    Độ phức tạp: O(α)O(\alpha) với α\alpha là độ phức tạp phép nhân hai số lớn.

Cài đặt

#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

typedef vector < int > vi;

// Nạp chồng toán tử chèn luồng, dùng để in ra số lớn.
ostream &operator << (ostream &cout, const vi &a)
{
    for (auto d: a)
        cout << d;

    return cout;
}

// Chuyển từ long long sang vector < int >.
vi ll_to_vi(long long n)
{
    vi c;
    if (n == 0)
    {
        c.push_back(n);
        return c;
    }

    while (n)
    {
        c.push_back(n % 10);
        n /= 10;
    }

    reverse(c.begin(), c.end());

    return c;
}

// Xóa các số 0 vô nghĩa ở đầu.
void del_zero(vi &a)
{
    reverse(a.begin(), a.end());

    while (a.size() >= 2)
        if (a.back() == 0)
            a.pop_back();
        else
            break;

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

vi operator * (vi a, vi b)
{
    // Đảo ngược hai số trước để tiện tính toán.
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    // Resize trước mảng kết quả. Kết quả của tích có thể đạt tới số chữ số
    // bằng tổng độ dài của hai số ban đầu cộng lại và cộng thêm 1.
    vi c(a.size() + b.size() + 1);
    for (int i = 0; i < (int) a.size(); ++i)
        for (int j = 0; j < (int) b.size(); ++j)
        {
            c[i + j] += (a[i] * b[j]);
            c[i + j + 1] += (c[i + j] / 10);
            c[i + j] %= 10;
        }

    // Xử lý nốt phần giá trị nhớ chưa được cộng hết.
    // Mảng c hiện tại đang là mảng kết quả bị đảo ngược.
    c.push_back(0);
    for (int i = 0; i < (int) c.size() - 1; ++i)
    {
    	c[i + 1] += (c[i] / 10);
    	c[i] %= 10;
    }

    // Đảo ngược mảng c và xóa các chữ số 0 vô nghĩa ở đầu, ta sẽ thu được tích a * b.
    reverse(c.begin(), c.end());
    del_zero(c);

    return c;
}

void solution(long long a, long long b, long long c)
{
    // Sắp xếp lại 3 số a, b, c theo thứ tự tăng dần.
    if (a > b)
        swap(a, b);
    if (a > c)
        swap(a, c);
    if (b > c)
        swap(b, c);

    if (a < 0 && b < 0)
        cout << ll_to_vi(abs(a)) * ll_to_vi(abs(b));
    else
        cout << ll_to_vi(b) * ll_to_vi(c);
}

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

    long long a, b, c;
    cin >> a >> b >> c;

    solution(a, b, c);

    return 0;
}

    Như vậy, trong bài viết này chúng ta đã hoàn thành các kĩ thuật xử lý số nguyên lớn trong C++ liên quan tới phép nhân. Để tiếp tục theo dõi phần ba của series Xử lý số nguyên lớn trong C++, mời các bạn nhấn vào đây.

Bình luận
Vui lòng đăng nhập để bình luận
Một số bài viết liên quan