8.8K 673 107

Đã đăng vào thg 10 13, 2021 8:39 SA 7 phút đọc

16.3K

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 $a$ cho số nhỏ $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 $b$ ở đây sẽ ràng buộc không vượt quá $10^{18}$ . Trường hợp $b$ lớn hơn nữa nhưng vẫn là số nhỏ (chẳng hạn như $b = 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 $b$ 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 $1$ 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 $10$ .

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),$ với $n$ 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ố $a$ và $b,$ đều lưu ở kiểu vi.
Bước 2: Tạo một mảng $c$ để lưu kết quả phép nhân. Gọi số lượng chữ số của $a$ và $b$ lần lượt là $m$ và $n$ thì ta có nhận xét rằng kết quả của phép nhân $a \times b$ sẽ luôn có số lượng chữ số không vượt quá $m + n + 1,$ nên ta khởi tạo mảng $c$ với kích thước tương tự.
Bước 3: Duyệt qua các cặp chữ số $a_i, b_j \ (0 \le i < m, 0 \le j < n),$ cộng thêm kết quả $a_i \times b_j$ vào vị trí $c_{i + j}$ . Để tránh tràn số, ta sẽ đẩy luôn phần nhớ là $\left\lfloor{\frac{c_{i + j}}{10}}\right\rfloor$ sang vị trí $c_{i + j + 1},$ và chỉ giữ lại giá trị $c_{i + j} \text{ mod } 10$ ở vị trí $c_{i + j}$ .
Bước 4: Xử lý nốt các vị trí còn lớn hơn $10,$ đẩy giá trị nhớ sang hàng đằng trước và cuối cùng xóa các chữ số $0$ vô nghĩa ở đầu kết quả đi (do kĩ thuật code nên cần phải xóa chữ số $0$ 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 \times m),$ với $n$ và $m$ 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 $n$ . Một hoán vị của các số từ $1$ tới $n$ là một cách sắp xếp các số từ $1$ tới $n$ theo thứ tự nào đó. Ví dụ, với $n = 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\}$ .

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ừ $1$ tới $n?$

Input:

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

Ràng buộc:

$1 \le n \le 10^6$ .

Subtasks:

Subtask $1$ ( $30\%$ số điểm): $1 \le n \le 50$ .
Subtask $2$ ( $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ừ $1$ tới $n$ .

Sample Input:

Sample Output:

Ý 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 $n$ thành phần sẽ là $n!$ .

Với subtask $1$ 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,$ bài toán tính $n!$ với $n \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 $\text{factorial}$ là kết quả cuối, khởi tạo giá trị $1$ cho nó. Tiếp theo duyệt lần lượt các số $i$ từ $2$ tới $n$ rồi nhân $\text{factorial}$ với giá trị $i$ 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 \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ả $\text{factorial}$ có giá trị là $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,c$ và một số nguyên dương $M$ .

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?$

Ràng buộc:

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

Subtasks:

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

Ý tưởng

Với subtask $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,$ 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(\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.

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

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

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

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

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

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

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

Đề bài

Ý tưởng

Cài đặt

2. Tích lớn nhất

Đề bài

Ý tưởng

Cài đặt

Mục lục