Bài 9.4: Ước chung lớn nhất và bội chung nhỏ nhất trong C++

Chào mừng trở lại với series blog C++ của FullhouseDev! Trong bài học hôm nay, chúng ta sẽ cùng nhau tìm hiểu về hai khái niệm quen thuộc trong toán học nhưng cực kỳ hữu ích trong lập trình: Ước chung lớn nhất (ƯCLN) hay Greatest Common Divisor (GCD) và Bội chung nhỏ nhất (BCNN) hay Least Common Multiple (LCM).

Tại sao chúng ta cần quan tâm đến UCLN và BCNN trong lập trình? Chúng xuất hiện ở nhiều nơi hơn bạn nghĩ đấy! Từ việc tối giản phân số, giải các bài toán số học, cho đến các vấn đề liên quan đến lịch trình, đồng bộ hóa hay thậm chí trong các thuật toán mã hóa. C++ cung cấp cho chúng ta nhiều cách để tính toán hai giá trị này, từ việc tự cài đặt các thuật toán cơ bản đến sử dụng các hàm có sẵn cực kỳ tiện lợi.

Hãy cùng đi sâu vào chi tiết nhé!

1. Ước chung lớn nhất (ƯCLN / GCD)

Ước chung lớn nhất của hai hay nhiều số nguyên dương là số nguyên dương lớn nhất mà là ước của tất cả các số đó. Ký hiệu: UCLN(a, b) hoặc GCD(a, b).

Ví dụ:

  • Ước của 12 là: 1, 2, 3, 4, 6, 12
  • Ước của 18 là: 1, 2, 3, 6, 9, 18
  • Các ước chung của 12 và 18 là: 1, 2, 3, 6
  • Ước chung lớn nhất của 12 và 18 là: 6. Vậy UCLN(12, 18) = 6.
Các phương pháp tìm UCLN
Phương pháp 1: Duyệt từ số nhỏ nhất trở xuống (Naive Approach)

Đây là cách tiếp cận đơn giản và dễ hiểu nhất. Ta biết rằng UCLN của hai số a và b không thể lớn hơn số nhỏ hơn trong hai số đó. Vì vậy, ta có thể bắt đầu duyệt từ min(a, b) xuống 1. Số đầu tiên mà chia hết cho cả a và b chính là UCLN.

Hãy xem code minh họa:

#include <iostream>
#include <algorithm>
#include <cmath> // For abs

int ucln_duyet(int x, int y) {
    x = abs(x);
    y = abs(y);
    if (x == 0) return y;
    if (y == 0) return x;
    int m = min(x, y);
    for (int i = m; i >= 1; --i) {
        if (x % i == 0 && y % i == 0) {
            return i;
        }
    }
    return 1;
}

int main() {
    using namespace std;
    int a = 48, b = 18;
    cout << "UCLN cua " << a << " va " << b << " la: " << ucln_duyet(a, b) << endl;

    a = 7; b = 13;
    cout << "UCLN cua " << a << " va " << b << " la: " << ucln_duyet(a, b) << endl;

    return 0;
}

UCLN cua 48 va 18 la: 6
UCLN cua 7 va 13 la: 1

Giải thích:

  • Hàm ucln_duyet nhận hai số nguyên x và y.
  • Chúng ta sử dụng abs() để làm việc với giá trị tuyệt đối, đảm bảo xử lý cả số âm (mặc dù định nghĩa chuẩn thường là với số dương).
  • Kiểm tra trường hợp đặc biệt khi một trong hai số là 0. UCLN của một số và 0 là giá trị tuyệt đối của chính số đó.
  • Tìm giá trị nhỏ nhất giữa x và y bằng min.
  • Vòng lặp for bắt đầu từ m giảm dần về 1.
  • Điều kiện x % i == 0 && y % i == 0 kiểm tra xem i có phải là ước chung của cả x và y hay không.
  • Ngay khi tìm thấy số i thỏa mãn điều kiện này, đó chính là UCLN lớn nhất, và chúng ta trả về i.
  • Nếu vòng lặp kết thúc (chỉ xảy ra khi m ban đầu là 0, hoặc khi x và y là 0), hàm sẽ trả về 1 (trường hợp x=y=0 sẽ trả về 0 ở kiểm tra ban đầu, trường hợp x,y > 0 nhưng không tìm thấy ước chung nào khác ngoài 1).

Phương pháp này đơn giản nhưng không hiệu quả lắm với các số lớn vì nó có thể cần duyệt qua rất nhiều số.

Phương pháp 2: Thuật toán Euclid (Euclidean Algorithm)

Đây là thuật toán cổ điển và hiệu quả nhất để tìm UCLN. Nguyên lý của thuật toán dựa trên tính chất sau:

UCLN(a, b) = UCLN(b, a mod b) (với a > b, và a mod b là số dư khi chia a cho b)

Thuật toán lặp đi lặp lại việc thay thế cặp số (a, b) bằng cặp (b, a mod b) cho đến khi số thứ hai bằng 0. Khi đó, số thứ nhất chính là UCLN.

Ví dụ: Tìm UCLN(48, 18)

  1. UCLN(48, 18) = UCLN(18, 48 mod 18) = UCLN(18, 12)
  2. UCLN(18, 12) = UCLN(12, 18 mod 12) = UCLN(12, 6)
  3. UCLN(12, 6) = UCLN(6, 12 mod 6) = UCLN(6, 0)
  4. Số thứ hai bằng 0, vậy UCLN là số thứ nhất: 6.

Thuật toán Euclid có thể được cài đặt bằng đệ quy hoặc lặp.

Cài đặt đệ quy:

#include <iostream>
#include <cmath> // For abs

int ucln_dq(int x, int y) {
    x = abs(x);
    y = abs(y);
    if (y == 0) {
        return x;
    }
    return ucln_dq(y, x % y);
}

int main() {
    using namespace std;
    int a = 48, b = 18;
    cout << "UCLN (de quy) cua " << a << " va " << b << " la: " << ucln_dq(a, b) << endl;

    a = 101; b = 103;
    cout << "UCLN (de quy) cua " << a << " va " << b << " la: " << ucln_dq(a, b) << endl;

    return 0;
}

UCLN (de quy) cua 48 va 18 la: 6
UCLN (de quy) cua 101 va 103 la: 1

Giải thích:

  • Hàm đệ quy ucln_dq cũng xử lý giá trị tuyệt đối và trường hợp y == 0.
  • Trường hợp cơ sở (base case) của đệ quy là khi y bằng 0, ta trả về x.
  • Trường hợp đệ quy (recursive step) là gọi lại hàm với cặp số mới (y, x % y). Quá trình này tiếp diễn cho đến khi đạt được trường hợp cơ sở.

Cài đặt lặp (phi đệ quy):

#include <iostream>
#include <cmath> // For abs

int ucln_lap(int x, int y) {
    x = abs(x);
    y = abs(y);
    while (y != 0) {
        int t = y;
        y = x % y;
        x = t;
    }
    return x;
}

int main() {
    using namespace std;
    int a = 48, b = 18;
    cout << "UCLN (lap) cua " << a << " va " << b << " la: " << ucln_lap(a, b) << endl;

    a = 25; b = 5;
    cout << "UCLN (lap) cua " << a << " va " << b << " la: " << ucln_lap(a, b) << endl;

    return 0;
}

UCLN (lap) cua 48 va 18 la: 6
UCLN (lap) cua 25 va 5 la: 5

Giải thích:

  • Hàm ucln_lap sử dụng vòng lặp while.
  • Vòng lặp tiếp tục chừng nào y còn khác 0.
  • Bên trong vòng lặp, ta lưu giá trị hiện tại của y vào biến tạm t.
  • Cập nhật y thành số dư của x chia cho y (x % y).
  • Cập nhật x thành giá trị cũ của y (lưu trong t).
  • Quá trình này tương đương với bước đệ quy nhưng không sử dụng stack call.
  • Khi vòng lặp kết thúc (y bằng 0), giá trị cuối cùng của x chính là UCLN.

Thuật toán Euclid (dù là đệ quy hay lặp) nhanh hơn đáng kể so với phương pháp duyệt đơn giản, đặc biệt với các số lớn.

Phương pháp 3: Sử dụng gcd (Từ C++17)

May mắn thay, từ chuẩn C++17, thư viện chuẩn đã cung cấp sẵn hàm gcd trong header <numeric>. Đây là cách nên dùng nếu bạn làm việc với C++17 trở lên vì nó đã được tối ưu hóa và kiểm tra kỹ lưỡng.

#include <iostream>
#include <numeric>

int main() {
    using namespace std;
    int a = 48, b = 18;
    cout << "UCLN (gcd) cua " << a << " va " << b << " la: " << gcd(a, b) << endl;

    a = 100; b = 75;
    cout << "UCLN (gcd) cua " << a << " va " << b << " la: " << gcd(a, b) << endl;

    a = -12; b = 18;
    cout << "UCLN (gcd) cua " << a << " va " << b << " la: " << gcd(a, b) << endl;

    return 0;
}

UCLN (gcd) cua 48 va 18 la: 6
UCLN (gcd) cua 100 va 75 la: 25
UCLN (gcd) cua -12 va 18 la: 6

Giải thích:

  • Chỉ cần #include <numeric> và gọi gcd(a, b).
  • Hàm này tự động xử lý các trường hợp số âm và số 0 theo định nghĩa chuẩn (UCLN của a và b là UCLN của |a| và |b|).
  • Đây là cách ngắn gọn, an toàn và hiệu quả nhất để tìm UCLN trong C++ hiện đại.

2. Bội chung nhỏ nhất (BCNN / LCM)

Bội chung nhỏ nhất của hai hay nhiều số nguyên dương là số nguyên dương nhỏ nhất (khác 0) mà là bội của tất cả các số đó. Ký hiệu: BCNN(a, b) hoặc LCM(a, b).

Ví dụ:

  • Bội dương của 12 là: 12, 24, 36, 48, 60, 72, ...
  • Bội dương của 18 là: 18, 36, 54, 72, ...
  • Các bội chung dương của 12 và 18 là: 36, 72, ...
  • Bội chung nhỏ nhất của 12 và 18 là: 36. Vậy BCNN(12, 18) = 36.
Mối liên hệ giữa UCLN và BCNN

Có một công thức rất hữu ích liên kết UCLN và BCNN của hai số nguyên dương a và b:

UCLN(a, b) * BCNN(a, b) = |a * b|

Từ công thức này, ta có thể dễ dàng tính BCNN nếu đã biết UCLN:

BCNN(a, b) = (|a * b|) / UCLN(a, b)

Đây là phương pháp phổ biến nhất để tìm BCNN vì chúng ta đã có các thuật toán hiệu quả để tìm UCLN.

Lưu ý quan trọng: Khi tính (a * b) / UCLN(a, b), nếu a và b là các số rất lớn, tích a * b có thể bị tràn số (integer overflow) trước khi kịp chia cho UCLN. Để tránh điều này, một cách an toàn hơn là thực hiện phép chia trước phép nhân:

BCNN(a, b) = (|a| / UCLN(a, b)) * |b|

Hoặc tương đương BCNN(a, b) = (|b| / UCLN(a, b)) * |a|.

Hãy xem code minh họa sử dụng công thức này và giả sử chúng ta đã có hàm tính UCLN (ví dụ: gcd).

#include <iostream>
#include <numeric>
#include <cmath>

long long bcnn(long long x, long long y) {
    if (x == 0 || y == 0) {
        return 0;
    }
    long long ax = abs(x);
    long long ay = abs(y);
    long long ucln_val = gcd(ax, ay);
    return (ax / ucln_val) * ay;
}

int main() {
    using namespace std;
    long long a = 12, b = 18;
    cout << "BCNN cua " << a << " va " << b << " la: " << bcnn(a, b) << endl;

    a = 21; b = 6;
    cout << "BCNN cua " << a << " va " << b << " la: " << bcnn(a, b) << endl;

    a = 1000000; b = 1000001;
    cout << "BCNN cua " << a << " va " << b << " la: " << bcnn(a, b) << endl;

    a = -12; b = 18;
    cout << "BCNN cua " << a << " va " << b << " la: " << bcnn(a, b) << endl;

    return 0;
}

BCNN cua 12 va 18 la: 36
BCNN cua 21 va 6 la: 42
BCNN cua 1000000 va 1000001 la: 1000001000000
BCNN cua -12 va 18 la: 36

Giải thích:

  • Hàm bcnn nhận hai số x và y. Chúng ta sử dụng long long để có thể làm việc với các giá trị BCNN lớn hơn.
  • Trường hợp đặc biệt: BCNN của bất kỳ số nào với 0 là 0.
  • Lấy giá trị tuyệt đối của x và y để đảm bảo làm việc với số dương.
  • Sử dụng gcd để tìm UCLN của giá trị tuyệt đối của x và y.
  • Tính BCNN bằng công thức (|x| / UCLN(|x|, |y|)) * |y|. Công thức này an toàn hơn vì phép chia |x| / UCLN(|x|, |y|) luôn cho kết quả là một số nguyên và thường nhỏ hơn |x|, giúp giảm nguy cơ tràn số khi nhân với |y|.
Phương pháp 2: Sử dụng lcm (Từ C++17)

Tương tự như UCLN, C++17 cũng cung cấp sẵn hàm lcm trong header <numeric>.

#include <iostream>
#include <numeric>

int main() {
    using namespace std;
    long long a = 12, b = 18;
    cout << "BCNN (lcm) cua " << a << " va " << b << " la: " << lcm(a, b) << endl;

    a = 21; b = 6;
    cout << "BCNN (lcm) cua " << a << " va " << b << " la: " << lcm(a, b) << endl;

    a = 1000000; b = 1000001;
    cout << "BCNN (lcm) cua " << a << " va " << b << " la: " << lcm(a, b) << endl;

    a = -12; b = 18;
    cout << "BCNN (lcm) cua " << a << " va " << b << " la: " << lcm(a, b) << endl;

    a = 0; b = 5;
    cout << "BCNN (lcm) cua " << a << " va " << b << " la: " << lcm(a, b) << endl;

    return 0;
}

BCNN (lcm) cua 12 va 18 la: 36
BCNN (lcm) cua 21 va 6 la: 42
BCNN (lcm) cua 1000000 va 1000001 la: 1000001000000
BCNN (lcm) cua -12 va 18 la: 36
BCNN (lcm) cua 0 va 5 la: 0

Giải thích:

  • Chỉ cần #include <numeric> và gọi lcm(a, b).
  • Hàm này cũng tự động xử lý số âm và số 0 theo định nghĩa chuẩn (BCNN của a và b là BCNN của |a| và |b|, và BCNN của bất kỳ số nào với 0 là 0).
  • Tương tự như gcd, lcm là cách ngắn gọn, an toàn và hiệu quả nhất để tìm BCNN trong C++17 trở lên.

3. Ứng dụng trong thực tế

UCLN và BCNN tuy là khái niệm toán học cơ bản nhưng có nhiều ứng dụng thực tế trong lập trình:

  • Tối giản phân số: Chia tử số và mẫu số cho UCLN của chúng. Ví dụ: Phân số 12/18, UCLN(12, 18) = 6. Chia cả tử và mẫu cho 6 được 2/3.
  • Tìm mẫu số chung nhỏ nhất (LCD - Least Common Denominator): Khi cộng hoặc trừ phân số, BCNN của các mẫu số chính là mẫu số chung nhỏ nhất.
  • Bài toán lịch trình/Chu kỳ: Tìm thời điểm tiếp theo hai sự kiện lặp lại sẽ xảy ra đồng thời. Nếu sự kiện A lặp sau mỗi T_a đơn vị thời gian và sự kiện B lặp sau mỗi T_b đơn vị thời gian, chúng sẽ lặp lại đồng thời sau mỗi BCNN(T_a, T_b) đơn vị thời gian.
  • Trong các thuật toán lý thuyết số: UCLN và BCNN là nền tảng cho nhiều thuật toán phức tạp hơn.

Việc hiểu rõ UCLN, BCNN và cách tính toán chúng hiệu quả sẽ giúp bạn giải quyết nhiều vấn đề lập trình một cách thanh lịch và tối ưu hơn.

#include <iostream>
#include <numeric>
#include <cmath> // For abs

struct PS {
    int tu;
    int mau;

    void rut_gon() {
        if (mau < 0) {
            tu = -tu;
            mau = -mau;
        }
        int ucln_val = gcd(abs(tu), mau);
        tu /= ucln_val;
        mau /= ucln_val;
    }
};

int main() {
    using namespace std;
    PS p1 = {12, 18};
    cout << "Phan so goc: " << p1.tu << "/" << p1.mau << endl;
    p1.rut_gon();
    cout << "Phan so sau khi toi gian: " << p1.tu << "/" << p1.mau << endl;

    PS p2 = {-24, 36};
    cout << "Phan so goc: " << p2.tu << "/" << p2.mau << endl;
    p2.rut_gon();
    cout << "Phan so sau khi toi gian: " << p2.tu << "/" << p2.mau << endl;

    PS p3 = {15, -25};
    cout << "Phan so goc: " << p3.tu << "/" << p3.mau << endl;
    p3.rut_gon();
    cout << "Phan so sau khi toi gian: " << p3.tu << "/" << p3.mau << endl;

    return 0;
}

Phan so goc: 12/18
Phan so sau khi toi gian: 2/3
Phan so goc: -24/36
Phan so sau khi toi gian: -2/3
Phan so goc: 15/-25
Phan so sau khi toi gian: -3/5

Giải thích:

  • Struct PS lưu tử số và mẫu số.
  • Hàm rut_gon() đầu tiên đảm bảo mẫu số là dương bằng cách đổi dấu cả tử và mẫu nếu cần.
  • Sau đó, nó tính UCLN của giá trị tuyệt đối của tử số và mẫu số bằng gcd. Lấy giá trị tuyệt đối của tử là quan trọng vì UCLN chỉ định nghĩa cho số dương, nhưng tử số có thể âm.
  • Cuối cùng, cả tử số và mẫu số được chia cho UCLN để tối giản phân số.

Đây chỉ là một ví dụ đơn giản, nhưng nó cho thấy cách UCLN có thể được áp dụng trực tiếp vào một vấn đề lập trình phổ biến.

Bài tập ví dụ: C++ Bài 4.B3: Kê chân bàn

Thấy chân bàn bị gập ghềnh nên Hiếu lấy một tờ giấy lần lượt gấp đôi lại nhiều lần để kê chân bàn. Giả sử tờ giấy có bề dày là \(n\) thì sau lần gấp đôi thứ nhất bề dày là \(2n\) , sau lần gấp đôi thứ \(2\) là \(4n\), lần thứ \(3\) là \(8n\),...

Nếu khoảng gập ghềnh là \(b\) thì Hiếu cần gấp đôi giấy bao nhiêu lần để kê chân bàn ít bị gập ghềnh nhất?

INPUT FORMAT

Dòng đầu tiên chứa hai giá trị \(n,b\) \((1 \leq a, b \leq 10^9)\).

OUTPUT FORMAT

Ví dụ 1:

Input
1 4
Ouput
2

Ví dụ 2:

Input
2 5
Output
1

Giải thích ví dụ mẫu:

  • Ví dụ 1:

    • Input: 1 4
    • Giải thích: Sau 2 lần gấp đôi, bề dày giấy là 4, đủ để kê chân bàn có khoảng gập ghềnh là 4.

  • Ví dụ 2:

    • Input: 2 5
    • Giải thích: Sau 1 lần gấp đôi, bề dày giấy là 4, đủ để kê chân bàn có khoảng gập ghềnh là 5.

1. Phân tích bài toán:

  • Bạn bắt đầu với một tờ giấy có bề dày ban đầu là n.
  • Mỗi lần gấp đôi, bề dày tăng gấp đôi.
  • Sau k lần gấp, bề dày sẽ là n * 2^k.
  • Khoảng gập ghềnh cần kê là b.
  • Mục tiêu là tìm số lần gấp k ít nhất sao cho bề dày sau khi gấp (n * 2^k) đủ để kê, tức là n * 2^k >= b.
  • Các giá trị n và b có thể lên tới 10^9, nên cần sử dụng kiểu dữ liệu có thể chứa được các giá trị lớn.

2. Xác định phương pháp giải:

Bài toán yêu cầu tìm số lần gấp k nhỏ nhất để đạt được một điều kiện (n * 2^k >= b). Bề dày tăng theo lũy thừa của 2, đây là một sự tăng trưởng nhanh chóng. Ta có thể mô phỏng trực tiếp quá trình gấp giấy.

Bắt đầu từ 0 lần gấp, kiểm tra bề dày. Nếu chưa đủ, tăng số lần gấp lên 1 và tính bề dày mới (gấp đôi bề dày hiện tại), rồi kiểm tra lại. Lặp lại quá trình này cho đến khi bề dày đủ để kê (>= b).

3. Hướng dẫn các bước thực hiện (không code hoàn chỉnh):

  • Bước 1: Đọc dữ liệu đầu vào.

    • Đọc hai số nguyên n và b.
    • Vì n và b có thể lớn (10^9), và bề dày sau khi gấp có thể vượt quá int, hãy sử dụng kiểu dữ liệu long long cho n và b, cũng như biến lưu trữ bề dày hiện tại.

  • Bước 2: Khởi tạo.

    • Khởi tạo một biến để lưu trữ số lần gấp hiện tại, bắt đầu từ 0.
    • Khởi tạo một biến để lưu trữ bề dày hiện tại, bắt đầu bằng giá trị n đọc từ input. Đảm bảo biến này cũng là long long.

  • Bước 3: Lặp và kiểm tra.

    • Sử dụng một vòng lặp (ví dụ: while) để tiếp tục quá trình gấp giấy chừng nào bề dày hiện tại còn nhỏ hơn khoảng gập ghềnh b.
    • Điều kiện của vòng lặp sẽ là: bề dày hiện tại < b.

  • Bước 4: Cập nhật trong mỗi lần lặp.

    • Bên trong vòng lặp (khi bề dày chưa đủ):
      • Tăng số lần gấp hiện tại lên 1.
      • Nhân đôi bề dày hiện tại. bề dày hiện tại = bề dày hiện tại * 2; hoặc bề dày hiện tại *= 2;.

  • Bước 5: Kết thúc và xuất kết quả.

    • Khi vòng lặp kết thúc, điều đó có nghĩa là bề dày hiện tại đã đạt hoặc vượt quá b.
    • Số lần gấp tại thời điểm vòng lặp dừng lại chính là số lần gấp tối thiểu cần thiết.
    • In ra giá trị của biến đếm số lần gấp.

4. Lưu ý khi triển khai bằng C++:

  • Sử dụng thư viện <iostream> cho việc nhập/xuất chuẩn (cin, cout).
  • Khai báo biến n, b, biến lưu bề dày hiện tại với kiểu long long. Biến đếm số lần gấp có thể là int vì số lần gấp sẽ không quá lớn (logarit cơ số 2 của 10^9 * 10^9 không quá lớn, khoảng 60), nhưng dùng long long cũng an toàn.
  • Đảm bảo phép nhân bề dày hiện tại với 2 không bị tràn số bằng cách sử dụng long long.

Ví dụ minh họa cách suy nghĩ (không phải code):

Input: n=2, b=5

  1. n=2, b=5.
  2. folds = 0, current_thickness = 2.
  3. Kiểm tra current_thickness < b: 2 < 5 -> True.
  4. Vào vòng lặp:
    • folds = 1.
    • current_thickness = 2 * 2 = 4.
  5. Kiểm tra current_thickness < b: 4 < 5 -> True.
  6. Vào vòng lặp:
    • folds = 2.
    • current_thickness = 4 * 2 = 8.
  7. Kiểm tra current_thickness < b: 8 < 5 -> False.
  8. Vòng lặp kết thúc.
  9. In ra folds, là 2.

Lưu ý về Ví dụ 2 trong đề bài: Ví dụ 2 trong đề bài (Input: 2 5, Output: 1) mâu thuẫn với quy tắc "bề dày >= b" và cách hoạt động của Ví dụ 1 (Input: 1 4, Output: 2, nơi bề dày 4 >= 4). Dựa trên mô tả bài toán "bề dày là \(n\) thì sau lần gấp đôi thứ nhất bề dày là \(2n\)..." và mục tiêu "kê chân bàn ít bị gập ghềnh nhất" (ngầm hiểu là cần đủ bề dày), giải pháp n * 2^k >= b là cách hiểu hợp lý nhất cho một bài tập lập trình cơ bản. Rất có thể ví dụ 2 có sai sót trong đề bài hoặc phần giải thích. Hãy code theo logic n * 2^k >= b.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.