GCD và LCM trong C++

1. GCD và LCM là gì?

Trong toán học:

GCD = Greatest Common Divisor = Ước chung lớn nhất (UCLN)
LCM = Least Common Multiple = Bội chung nhỏ nhất (BCNN)

Hai khái niệm này xuất hiện rất thường xuyên trong các bài toán lập trình, đặc biệt là các bài về số nguyên, phân số, chu kỳ và chia hết.

2. Ước là gì?

Trước khi hiểu GCD, cần hiểu khái niệm ước.

Một số a được gọi là ước của b nếu b chia hết cho a.

Nói cách khác:

b % a == 0

Ví dụ:

12 % 1 = 0
12 % 2 = 0
12 % 3 = 0
12 % 4 = 0
12 % 6 = 0
12 % 12 = 0

Vậy các ước của 12 là:

1, 2, 3, 4, 6, 12

3. Ước chung là gì?

Ước chung của hai hay nhiều số là một số có thể chia hết cho tất cả các số đó.

Ví dụ xét:

12 và 18

Các ước của 12:

1, 2, 3, 4, 6, 12

Các ước của 18:

1, 2, 3, 6, 9, 18

Các số xuất hiện trong cả hai danh sách là:

1, 2, 3, 6

Đây là các ước chung của 12 và 18.

4. Ước chung lớn nhất - GCD

Trong các ước chung, số lớn nhất được gọi là:

Ước chung lớn nhất (UCLN)

Với:

12 và 18

Các ước chung là:

1, 2, 3, 6

Số lớn nhất là:

Do đó:

GCD(12, 18) = 6

Ký hiệu

Trong toán học thường viết:

gcd(12, 18) = 6

Trong C++:

C++

gcd(12, 18)

5. GCD trong C++

Từ C++17, thư viện chuẩn cung cấp sẵn hàm std::gcd().

Cần thêm:

C++

#include <numeric>

Ví dụ:

C++

#include <iostream>
#include <numeric>

using namespace std;

int main() {
    int a = 12;
    int b = 18;

    cout << gcd(a, b);

    return 0;
}

Kết quả:

6. Nhập GCD từ bàn phím

Ví dụ:

C++

#include <iostream>
#include <numeric>

using namespace std;

int main() {
    int a, b;

    cin >> a >> b;

    cout << gcd(a, b);

    return 0;
}

Nếu nhập:

24 36

Kết quả:

Bởi vì:

Ước của 24: 1 2 3 4 6 8 12 24
Ước của 36: 1 2 3 4 6 9 12 18 36

Ước chung lớn nhất là:

7. Thuật toán Euclid

Nếu không sử dụng std::gcd(), ta có thể tự tìm GCD bằng thuật toán Euclid.

Công thức quan trọng:

gcd(a, b) = gcd(b, a % b)

Lặp lại cho đến khi số thứ hai bằng 0.

Ví dụ:

gcd(48, 18)

Ta thực hiện:

48 % 18 = 12
18 % 12 = 6
12 % 6  = 0

Khi đó:

GCD = 6

8. Tự viết hàm GCD

C++

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }

    return a;
}

Sử dụng:

C++

#include <iostream>

using namespace std;

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }

    return a;
}

int main() {
    cout << gcd(48, 18);

    return 0;
}

Kết quả:

9. Bội là gì?

Một số a được gọi là bội của b nếu a chia hết cho b.

Ví dụ các bội của 5 là:

5, 10, 15, 20, 25, 30, ...

Vì:

10. Bội chung là gì?

Bội chung của hai số là một số đồng thời là bội của cả hai số.

Ví dụ:

12 và 18

Các bội của 12:

12, 24, 36, 48, 60, 72, ...

Các bội của 18:

18, 36, 54, 72, 90, ...

Các số xuất hiện ở cả hai dãy là:

36, 72, ...

Đây là các bội chung.

11. Bội chung nhỏ nhất - LCM

Trong các bội chung, số nhỏ nhất khác 0 được gọi là:

Bội chung nhỏ nhất (BCNN)

Với:

12 và 18

Bội chung nhỏ nhất là:

Do đó:

LCM(12, 18) = 36

Trong C++, ta có thể sử dụng:

C++

lcm(a, b)

12. LCM trong C++

Từ C++17, C++ cung cấp sẵn std::lcm() trong thư viện <numeric>.

Ví dụ:

C++

#include <iostream>
#include <numeric>

using namespace std;

int main() {
    int a = 12;
    int b = 18;

    cout << lcm(a, b);

    return 0;
}

Kết quả:

13. Nhập hai số và tìm LCM

C++

#include <iostream>
#include <numeric>

using namespace std;

int main() {
    int a, b;

    cin >> a >> b;

    cout << lcm(a, b);

    return 0;
}

Ví dụ nhập:

12 18

Kết quả:

14. Mối quan hệ giữa GCD và LCM

Đây là công thức rất quan trọng:

GCD(a, b) × LCM(a, b) = a × b

Do đó:

LCM(a, b) = a / GCD(a, b) × b

Ví dụ:

a = 12
b = 18

Ta có:

GCD(12, 18) = 6

Suy ra:

LCM = 12 / 6 × 18
    = 2 × 18
    = 36

15. Tự viết hàm LCM

Ta có thể viết:

C++

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

Ví dụ đầy đủ:

C++

#include <iostream>

using namespace std;

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }

    return a;
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

int main() {
    long long a, b;

    cin >> a >> b;

    cout << "GCD = " << gcd(a, b) << '\n';
    cout << "LCM = " << lcm(a, b) << '\n';

    return 0;
}

Nếu nhập:

12 18

Kết quả:

GCD = 6
LCM = 36

16. Tại sao LCM nên viết `a / gcd(a,b) * b`?

Có hai cách:

C++

a * b / gcd(a, b)

và:

C++

a / gcd(a, b) * b

Nên ưu tiên:

C++

a / gcd(a, b) * b

Bởi vì nếu a và b lớn, phép nhân:

C++

a * b

có thể làm số bị vượt giới hạn kiểu dữ liệu trước khi thực hiện phép chia.

Ví dụ:

C++

long long ans = a / gcd(a, b) * b;

thường an toàn hơn:

C++

long long ans = a * b / gcd(a, b);

17. Sử dụng trực tiếp GCD và LCM trong C++

Nếu compiler hỗ trợ C++17, cách đơn giản nhất là:

C++

#include <iostream>
#include <numeric>

using namespace std;

int main() {
    long long a, b;

    cin >> a >> b;

    cout << "GCD = " << gcd(a, b) << '\n';
    cout << "LCM = " << lcm(a, b) << '\n';

    return 0;
}

Ví dụ:

Input:
24 36

Output:
GCD = 12
LCM = 72

18. GCD và LCM thường được dùng vào đâu?

18.1. Rút gọn phân số

Ví dụ:

24 / 36

Tìm:

GCD(24, 36) = 12

Chia cả tử và mẫu cho 12:

24 / 36 = 2 / 3

Trong C++:

C++

int g = gcd(tu, mau);

tu /= g;
mau /= g;

18.2. Tìm chu kỳ chung

Giả sử:

Đèn A nhấp nháy mỗi 6 giây.
Đèn B nhấp nháy mỗi 8 giây.

Sau bao lâu chúng cùng nhấp nháy lại?

Ta cần tìm:

LCM(6, 8)

Kết quả:

Vậy sau 24 giây chúng lại cùng nhấp nháy.

Đây là một dạng bài rất thường gặp trong lập trình.

18.3. Kiểm tra chia hết

GCD cũng thường được dùng để kiểm tra các tính chất liên quan đến chia hết.

Ví dụ:

C++

if (gcd(a, b) == 1) {
    cout << "Hai so nguyen to cung nhau";
}

Nếu:

gcd(a, b) = 1

thì a và b được gọi là nguyên tố cùng nhau.

Ví dụ:

8 và 15

Có:

gcd(8, 15) = 1

nên 8 và 15 là hai số nguyên tố cùng nhau.

19. So sánh GCD và LCM

Khái niệmÝ nghĩaVí dụ với 12 và 18
Ước	Số chia hết một số khác	1, 2, 3, 4, 6, 12
Ước chung	Ước của cả hai số	1, 2, 3, 6
GCD / UCLN	Ước chung lớn nhất	6
Bội	Các số chia hết cho một số	12, 24, 36, ...
Bội chung	Bội của cả hai số	36, 72, ...
LCM / BCNN	Bội chung nhỏ nhất khác 0	36

20. Những điều cần nhớ khi làm bài C++

GCD

C++

#include <numeric>

gcd(a, b);

LCM

C++

#include <numeric>

lcm(a, b);

Cả hai đều nằm trong:

C++

#include <numeric>

và được hỗ trợ từ:

C++17

21. Công thức quan trọng cần thuộc

GCD

gcd(a, b) = gcd(b, a % b)

LCM

lcm(a, b) = a / gcd(a, b) × b

Mối quan hệ

gcd(a, b) × lcm(a, b) = a × b

22. Ví dụ tổng hợp

Cho hai số:

a = 48
b = 18

Ta tìm GCD:

48 % 18 = 12
18 % 12 = 6
12 % 6 = 0

Vậy:

GCD = 6

LCM = 48 / 6 × 18
    = 8 × 18
    = 144

Kết quả:

GCD = 6
LCM = 144

Kiểm tra:

6 × 144 = 864
48 × 18 = 864

Hai vế bằng nhau, công thức chính xác.

23. Mẫu code nên nhớ

Nếu đang làm bài lập trình thi đấu, bạn có thể nhớ mẫu sau:

C++

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

int main() {
    long long a, b;
    cin >> a >> b;

    cout << gcd(a, b) << '\n';
    cout << lcm(a, b) << '\n';

    return 0;
}

Hoặc nếu đề yêu cầu tự cài đặt:

C++

long long gcd(long long a, long long b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

Tóm tắt

GCD = Ước chung lớn nhất
LCM = Bội chung nhỏ nhất

Ví dụ:

12 và 18

GCD = 6
LCM = 36

Trong C++17:

C++

#include <numeric>

gcd(a, b);
lcm(a, b);

Đây là hai hàm rất đáng nhớ khi làm bài thuật toán vì chúng xuất hiện trong các bài về phân số, chia hết, chu kỳ, số nguyên tố cùng nhau và các bài toán số học.

Bình luận

Tải bình luận...

Không có bình luận nào.

THT Khánh Hoà

GCD và LCM trong C++

1. GCD và LCM là gì?

2. Ước là gì?

3. Ước chung là gì?

4. Ước chung lớn nhất - GCD

Ký hiệu

5. GCD trong C++

6. Nhập GCD từ bàn phím

7. Thuật toán Euclid

8. Tự viết hàm GCD

9. Bội là gì?

10. Bội chung là gì?

11. Bội chung nhỏ nhất - LCM

12. LCM trong C++

13. Nhập hai số và tìm LCM

14. Mối quan hệ giữa GCD và LCM

15. Tự viết hàm LCM

16. Tại sao LCM nên viết a / gcd(a,b) * b?

17. Sử dụng trực tiếp GCD và LCM trong C++

18. GCD và LCM thường được dùng vào đâu?

18.1. Rút gọn phân số

18.2. Tìm chu kỳ chung

18.3. Kiểm tra chia hết

19. So sánh GCD và LCM

20. Những điều cần nhớ khi làm bài C++

GCD

LCM

21. Công thức quan trọng cần thuộc

GCD

LCM

Mối quan hệ

22. Ví dụ tổng hợp

23. Mẫu code nên nhớ

Tóm tắt

Bình luận

16. Tại sao LCM nên viết `a / gcd(a,b) * b`?