8.8K 673 107

Đã đăng vào thg 3 8, 2023 7:16 SA 11 phút đọc

3.0K

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

Đây là phần ba 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ừ và nhân 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 các bài viết trước đây:

Trong bài viết có sử dụng lại một số khái niệm của các 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 Chia trên tập số lớn!

I. Các phép toán Chia

Toàn bộ các cài đặt về phép chia cũng sẽ sử dụng kĩ thuật biểu diễn số nguyên lớn bằng mảng, nên trước khi đi vào các phép toán chia, chúng ta sẽ xây dựng trước một số hàm đặc biệt sẽ sử dụng trong các cài đặt bên dưới:

Hàm chuyển đổi từ số nguyên bình thường sang số lớn kiểu mảng:

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;
}

Hàm cân bằng độ dài hai số lớn và xóa chữ số

0

vô nghĩa ở đầu một số lớn:

// Viết thêm các số 0 ở đầu.
void add_zero(vi &a, int sz) 
{
    // Đầu tiên đảo ngược hai số để tối ưu thời gian khi thêm phần tử.
    reverse(a.begin(), a.end()); 

    while (a.size() < sz) 
        a.push_back(0); 

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

// Cân bằng độ dài hai số a và b bằng cách thêm các số 0 vào đầu.
void change(vi &a, vi &b) 
{ 
    int sz = max(a.size(), b.size());
    add_zero(a, sz);
    add_zero(b, sz);
}

// 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());
}

Các code So sánh, Cộng, Trừ, Nhân hai số lớn bằng mảng: Các bạn tái sử dụng lại từ các đoạn code ở các bài viết trước đây (link ở phần I).

1. Phép chia lấy thương nguyên một số lớn cho một số nhỏ

Ý tưởng

Ta sử dụng cách chia giống như học sinh tiểu học đặt tính phép chia: Liên tục lấy từng chữ số của số bị chia gộp vào một biến $cur,$ sau đó chia $cur$ cho số chia, ghi thương nguyên vào một mảng kết quả, sau đó gán $cur$ bằng số dư của phép chia vừa thực hiện.

Cài đặt

// Nạp chồng toán tử / cho một số lớn và một số nhỏ.
// Có thể đổi kiểu số nhỏ thành int tùy ý.
vi operator / (vi a, long long b) 
{
    long long cur = 0;
    vi c;
    for (int d: a) 
    {
        cur = cur * 10 + d;
        c.push_back (cur / b);
        cur %= b;
    }
	
    del_zero(c);
	
    return c;
}

Độ phức tạp: $O(n)$ với $n$ là số chữ số của số lớn $a$ .

2. Phép chia lấy thương nguyên giữa hai số lớn

Ý tưởng

Đối với phép chia hai số lớn, ta sẽ sử dụng thuật toán tìm kiếm nhị phân. Ý tưởng là tìm kiếm nhị phân giá trị $res$ lớn nhất sao cho $res$ nhân với số chia sẽ có kết quả gần với số bị chia nhất có thể. Tuy nhiên, các thao tác nhân, chia, so sánh trong thuật toán đều sẽ phải sử dụng số lớn theo, vì vậy đây là phép toán cài đặt phức tạp nhất.

Trong cài đặt dưới đây, chúng ta sẽ phải tái sử dụng lại các đoạn code So sánh hai số lớn, Cộng hai số lớn, Nhân hai số lớn, Chia số lớn cho số nhỏ và Trừ hai số lớn.

Cài đặt

// Nạp chồng toán tử / cho hai số lớn.
vi operator / (vi a, vi b) 
{
    vi res;
    res.push_back(0); // Ban đầu res = 0
	
    vi l, r;
    l.push_back(1); // Gán l = 1.
    vi one = int_to_vi(1);
    r = a; // Gán r = a.
    while (l <= r) 
    {
        vi mid = (l + r) / 2;
        if (mid * b <= a) 
        {
            res = mid;
            l = mid + one;
        }
        else 
            r = mid - one;
    }
	
    return res;
}

Độ phức tạp: Bằng với độ phức tạp của các phép toán So sánh, Cộng, Trừ, Chia số lớn cho số nhỏ và Nhân hai số lớn cộng lại.

3. Phép chia lấy dư một số lớn cho một số nhỏ

Ý tưởng

Đối với phép chia lấy dư của một số lớn cho một số nhỏ, ý tưởng khá đơn giản dựa trên ý tưởng sau: Khi thêm chữ số $d$ vào cuối số $a,$ thì giá trị của số mới sau khi mod cho một số nguyên $b$ sẽ là:

$(n \times 10 + d) \text{ mod } m$

Cài đặt

// Nạp chồng toán tử % cho một số lớn và một số nhỏ
// Có thể sửa lại số nhỏ thành int hoặc các kiểu số khác tùy ý.
long long operator % (vi a, long long b) 
{
    long long res = 0;
    for (int d: a)
        res = (res * 10 + d) % b;
		
    return res;
}

Độ phức tạp: $O(n)$ với $n$ là số chữ số của số lớn $a$ .

4. Phép chia lấy dư hai số lớn

Ý tưởng

Đối với phép chia lấy dư hai số lớn, ta sẽ phải sử dụng thêm cả phép toán chia lấy thương nguyên giữa hai số lớn và trừ hai số lớn. Ý tưởng dựa trên công thức:

$a \text{ mod } b = a - \left\lfloor{\frac{a}{b}}\right\rfloor \times b$

Như vậy trước đó các bạn đã phải nạp chồng các toán tử / và - cho hai số nguyên lớn kiểu vi để tái sử dụng chúng.

Cài đặt

// Nạp chồng toán tử % cho hai số lớn a và b.
vi operator % (vi a, vi b)
{
    vi c = a / b * b;
    return a - c;
}

Độ phức tạp: Bằng với độ phức tạp của phép Nhân hai số lớn, phép Chia hai số lớn và phép Trừ hai số lớn cộng lại.

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

Dưới đây là chương trình gồm đầy đủ các thao tác chia 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ử trích luồng, dùng để nhập vào số lớn.
istream &operator >> (istream &cin, vi &number)
{
    string s;
    cin >> s;

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

    return cin;
}

// 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;
} 

// Viết thêm các số 0 ở đầu.
void add_zero(vi &a, int sz) 
{
    // Đầu tiên đảo ngược hai số để tối ưu thời gian khi thêm phần tử.
    reverse(a.begin(), a.end()); 

    while (a.size() < sz) 
        a.push_back(0); 

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

// Cân bằng độ dài hai số a và b bằng cách thêm các số 0 vào đầu.
void change(vi &a, vi &b) 
{ 
    int sz = max(a.size(), b.size());
    add_zero(a, sz);
    add_zero(b, sz);
}

// 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());
}

bool operator <= (vi a, vi b) 
{
    change(a, b);
	
    for (int i = 0; i < a.size(); ++i) 
        if (a[i] < b[i]) 
            return true;
        else if (a[i] > b[i]) 
            return false;
	
    return true;
}

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;
}
	
// Phép toán cộng.
vi operator + (vi a, vi b) 
{
    change(a, b);

    int sz = a.size();
    vi c;
	
    int rem = 0; 
    for (int i = sz - 1; i >= 0; --i) 
    {
        int x = a[i] + b[i] + rem;
        rem = x / 10; 
        x %= 10;
        c.push_back(x);
    }
	
    c.push_back(rem);
    reverse(c.begin(), c.end());
    del_zero(c);
	
    return c;
}

vi operator - (vi a, vi b) 
{
    change(a, b);
	
    int sz = a.size();
    vi c;
	
    int rem = 0;
    for (int i = sz - 1; i >= 0; --i) 
    {
        int x = a[i] - b[i] - rem;
        if (x < 0) 
        {
            x += 10;
            rem = 1;
        }
        else 
            rem = 0;
		
        c.push_back(x);
    }
	
    reverse(c.begin(), c.end());
    del_zero(c);
	
    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;
}

// Nạp chồng toán tử / cho một số lớn và một số nhỏ.
// Có thể đổi kiểu số nhỏ thành int tùy ý.
vi operator / (vi a, long long b) 
{
    long long cur = 0;
    vi c;
    for (int d: a) 
    {
        cur = cur * 10 + d;
        c.push_back (cur / b);
        cur %= b;
    }
	
    del_zero(c);
	
    return c;
}

// Nạp chồng toán tử / cho hai số lớn.
vi operator / (vi a, vi b) 
{
    vi res;
    res.push_back(0); // Ban đầu res = 0
	
    vi l, r;
    l.push_back(1); // Gán l = 1.
    vi one = int_to_vi(1);
    r = a; // Gán r = a.
    while (l <= r) 
    {
        vi mid = (l + r) / 2;
        if (mid * b <= a) 
        {
            res = mid;
            l = mid + one;
        }
        else 
            r = mid - one;
    }
	
    return res;
}

// Nạp chồng toán tử % cho một số lớn và một số nhỏ
// Có thể sửa lại số nhỏ thành int hoặc các kiểu số khác tùy ý.
long long operator % (vi a, long long b) 
{
    long long res = 0;
    for (int d: a)
        res = (res * 10 + d) % b;
		
    return res;
}

// Nạp chồng toán tử % cho hai số lớn a và b.
vi operator % (vi a, vi b)
{
    vi c = a / b * b;
    return a - c;
}

main()
{
    vi a, b;
    long long n;
	
    cin >> a >> b;
    cin >> n;
	
    // In ra kết quả các phép toán Chia đã xây dựng.
    cout << a / n << '\n';
    cout << a / b << '\n';
    cout << a % n << '\n';
    cout << a % b << '\n';
	
    return 0;
}

II. Bài tập minh họa

1. Bội chung nhỏ nhất

Đề bài

Cho hai số nguyên dương $a$ và $b$ .

Yêu cầu: Hãy tính bội chung nhỏ nhất của $a$ và $b?$

Input:

Gồm một dòng chứa hai số nguyên dương $a$ và $b$ .

Ràng buộc:

$1 \le a, b \le 10^{150}$ .

Output:

In ra trên một dòng kết quả của bài toán.

Sample Input:

4 7

Sample Output:

Ý tưởng

Công thức tính $\text{LCM}(a,b)$ là $\frac{a \times b}{\text{GCD}(a,b)}$ .

Để tính $\text{GCD}(a,b),$ ta có thể dùng giải thuật Euclid. Đây là thuật toán khá cơ bản nên tôi sẽ không nhắc lại. Do $a,b$ rất lớn nên ta cần sử dụng tính toán số lớn cho các phép nhân, chia và mod.

Độ phức tạp: $O(\log b \times \alpha)$ với $\alpha$ là độ phức tạp giải thuật mod hai số lớn.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

typedef vector < int > vi;

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

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

    return cin;
}

// 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;
}

// Viết thêm các số 0 ở đầu.
void add_zero(vi &a, int sz)
{
    // Đầu tiên đảo ngược hai số để tối ưu thời gian khi thêm phần tử.
    reverse(a.begin(), a.end());

    while ((int) a.size() < sz)
        a.push_back(0);

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

// Cân bằng độ dài hai số a và b bằng cách thêm các số 0 vào đầu.
void change(vi &a, vi &b)
{
    int sz = max(a.size(), b.size());
    add_zero(a, sz);
    add_zero(b, sz);
}

// 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());
}

bool operator <= (vi a, vi b)
{
    change(a, b);

    for (int i = 0; i < (int) a.size(); ++i)
        if (a[i] < b[i])
            return true;
        else if (a[i] > b[i])
            return false;

    return true;
}

// Chuyển từ int sang vi.
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;
}

// Phép toán cộng.
vi operator + (vi a, vi b)
{
    change(a, b);

    int sz = a.size();
    vi c;

    int rem = 0;
    for (int i = sz - 1; i >= 0; --i)
    {
        int x = a[i] + b[i] + rem;
        rem = x / 10;
        x %= 10;
        c.push_back(x);
    }

    c.push_back(rem);
    reverse(c.begin(), c.end());
    del_zero(c);

    return c;
}

// Phép toán trừ.
vi operator - (vi a, vi b)
{
    change(a, b);

    int sz = a.size();
    vi c;

    int rem = 0;
    for (int i = sz - 1; i >= 0; --i)
    {
        int x = a[i] - b[i] - rem;
        if (x < 0)
        {
            x += 10;
            rem = 1;
        }
        else
            rem = 0;

        c.push_back(x);
    }

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

    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;
}

// Nạp chồng toán tử / cho một số lớn và một số nhỏ.
// Có thể đổi kiểu số nhỏ thành int tùy ý.
vi operator / (vi a, long long b)
{
    long long cur = 0;
    vi c;
    for (int d: a)
    {
        cur = cur * 10 + d;
        c.push_back (cur / b);
        cur %= b;
    }

    del_zero(c);

    return c;
}

// Nạp chồng toán tử / cho hai số lớn.
vi operator / (vi a, vi b)
{
    vi res;
    res.push_back(0); // Ban đầu res = 0

    vi l, r;
    l.push_back(1); // Gán l = 1.
    vi one = int_to_vi(1);
    r = a; // Gán r = a.
    while (l <= r)
    {
        vi mid = (l + r) / 2;
        if (mid * b <= a)
        {
            res = mid;
            l = mid + one;
        }
        else
            r = mid - one;
    }

    return res;
}

// Nạp chồng toán tử % cho hai số lớn a và b.
vi operator % (vi a, vi b)
{
    vi c = a / b * b;
    return a - c;
}

vi gcd(vi a, vi b)
{
    vi zero = int_to_vi(0);

    // Toán tử != không cần nạp chồng, do hai vector có thể so sánh khác trực tiếp.
    while (b != zero)
    {
        vi r = a % b;
        a = b;
        b = r;
    }

    return a;
}

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

    vi a, b;
    cin >> a >> b;

    cout << a * b / gcd(a,b) << endl;

    return 0;
}

2. Tìm căn bậc hai

Đề bài

Cho một số nguyên dương $n$ . Kí hiệu $\left\lfloor {a} \right\rfloor$ có nghĩa là phần nguyên của số $a$ . Ví dụ $\left\lfloor {6.8} \right\rfloor = 6$ .

Yêu cầu: Hãy in ra $\left\lfloor {\sqrt n} \right\rfloor?$

Input:

Gồm một dòng chứa duy nhất số nguyên dương $n$ .

Ràng buộc:

$n \le 10^{200}$ .

Output:

In ra trên một dòng kết quả của bài toán.

Sample Input:

Sample Output:

Ý tưởng

Do $n$ lớn nên ta không thể sử dụng trực tiếp hàm sqrt() để tìm căn bậc hai của $n$ . Thay vào đó, ta sử dụng ý tưởng tìm kiếm nhị phân kết quả, tìm ra số $d$ lớn nhất thỏa mãn $d \times d \le n$ .

Cách làm trên sẽ yêu cầu phải có xử lý số nguyên lớn, cụ thể là các phép toán nhân hai số lớn, nạp chồng các toán tử so sánh số lớn và cả các phép toán cộng hai số lớn, chia số lớn cho số nhỏ, trừ hai số lớn (ở bước tìm kiếm nhị phân). Nói chung đây là một bài toán dễ về ý tưởng nhưng cài đặt rất dài nếu các bạn sử dụng C++, hãy xem thêm ở cài đặt.

Độ phức tạp: $O(\log n \times \alpha)$ với $\alpha$ là tổng độ phức tạp các thao tác xử lý số lớn.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

typedef vector < int > vi;

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

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

    return cin;
}

// 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;
}

// Viết thêm các số 0 ở đầu.
void add_zero(vi &a, int sz)
{
    // Đầu tiên đảo ngược hai số để tối ưu thời gian khi thêm phần tử.
    reverse(a.begin(), a.end());

    while ((int) a.size() < sz)
        a.push_back(0);

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

// Cân bằng độ dài hai số a và b bằng cách thêm các số 0 vào đầu.
void change(vi &a, vi &b)
{
    int sz = max(a.size(), b.size());
    add_zero(a, sz);
    add_zero(b, sz);
}

// 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());
}

bool operator < (vi a, vi b)
{
    change(a, b);

    for (int i = 0; i < (int) a.size(); ++i)
        if (a[i] < b[i])
            return true;
        else if (a[i] > b[i])
            return false;

    return false;
}

bool operator <= (vi a, vi b)
{
    change(a, b);

    for (int i = 0; i < (int) a.size(); ++i)
        if (a[i] < b[i])
            return true;
        else if (a[i] > b[i])
            return false;

    return true;
}

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;
}

// Phép toán cộng.
vi operator + (vi a, vi b)
{
    change(a, b);

    int rem = 0;
    vi c;
    for (int i = a.size() - 1; i >= 0; --i)
    {
        int x = a[i] + b[i] + rem;
        rem = x / 10;
        x %= 10;
        c.push_back(x);
    }

    c.push_back(rem);
    reverse(c.begin(), c.end());
    del_zero(c);

    return c;
}

// Phép toán trừ.
vi operator - (vi a, vi b)
{
    change(a, b);

    int rem = 0;
    vi c;
    for (int i = a.size() - 1; i >= 0; --i)
    {
        int x = a[i] - b[i] - rem;
        if (x < 0)
        {
            x += 10;
            rem = 1;
        }
        else
            rem = 0;

        c.push_back(x);
    }

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

    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;
}

// Nạp chồng toán tử / cho một số lớn và một số nhỏ.
// Có thể đổi kiểu số nhỏ thành int tùy ý.
vi operator / (vi a, long long b)
{
    long long cur = 0;
    vi c;
    for (int d: a)
    {
        cur = cur * 10 + d;
        c.push_back (cur / b);
        cur %= b;
    }

    del_zero(c);

    return c;
}

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

    vi n;
    cin >> n;

    vi res;
    vi l = int_to_vi(1), r = n, one = int_to_vi(1);
    while (l <= r)
    {
        vi mid = (l + r) / 2;
        if (mid * mid <= n)
        {
            res = mid;
            l = mid + one;
        }
        else
            r = mid - one;
    }

    cout << res;

    return 0;
}

Như vậy tôi đã hướng dẫn các bạn chi tiết về các thao tác trên các số nguyên lớn trong C++. Nếu còn thắc mắc, các bạn có thể đọc thêm tài liệu ở các đường link mà tôi đã đính kèm dưới mục Tài liệu tham khảo. Nhìn chung, các bài toán liên quan tới số nguyên lớn thường là các bài toán không khó, số lớn được lồng ghép vào chỉ để làm tăng tính đánh đố của bài, nên các bạn chỉ cần ghi nhớ một trong hai phương pháp cài đặt là được rồi. Lời khuyên của người viết là các bạn hãy viết sẵn một template liên quan tới các phép toán trên số lớn, lưu riêng ra rồi tới khi cần chỉ lấy ra sử dụng thôi. Còn đối với những bạn có mục tiêu tham gia các kỳ thi Học sinh giỏi Tin học thì không có cách nào ngoài ghi nhớ code cả!

Toàn bộ các code về xử lý số nguyên lớn (bằng mảng lưu chữ số) trong 3 bài viết thuộc series này được upload tại đây, hãy xem lại khi cần thiết!

III. Tài liệu tham khảo

Viblo Viblo Algorithm

I. Các phép toán Chia

1. Phép chia lấy thương nguyên một số lớn cho một số nhỏ

Ý tưởng

Cài đặt

2. Phép chia lấy thương nguyên giữa hai số lớn

Ý tưởng

Cài đặt

3. Phép chia lấy dư một số lớn cho một số nhỏ

Ý tưởng

Cài đặt

4. Phép chia lấy dư hai số lớn

Ý tưởng

Cài đặt

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

II. Bài tập minh họa

1. Bội chung nhỏ nhất

Đề bài

Ý tưởng

Code mẫu

2. Tìm căn bậc hai

Đề bài

Ý tưởng

Code mẫu

III. Tài liệu tham khảo

Mục lục