Lập trình C/C++

Thuật toán tìm GCD (Greatest Common Divisor) và LCM (Least Common Multiple)

Posted on by Đỗ Thành
Học lập trình
04
Th2
View: 59

Thuật toán tìm ước chung lớn nhất GCD (Greatest Common Divisor) và Bội chung nhỏ nhất LCM (Least Common Multiple) của 2 số nguyên.

Giải thuật tìm GCD (Greatest Common Divisor)

Thuật toán phổ biến nhất để tìm GCD của hai số nguyên là Euclid Algorithm.

Mô tả thuật toán:

  • Nếu b = 0, thì GCD(a, b) = a.
  • Nếu b ≠ 0, thì GCD(a, b) = GCD(b, a % b).

Code C++ cho GCD bằng Euclid:

#include <iostream>
using namespace std;

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

int main() {
    int a, b;
    cout << "Nhap hai so a va b: ";
    cin >> a >> b;
    cout << "GCD cua " << a << " va " << b << " la: " << gcd(a, b) << endl;
    return 0;
}

Giải thuật tìm LCM (Least Common Multiple)

LCM của hai số a và b có thể được tính từ GCD theo công thức:

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

Code C++ cho LCM:

#include <iostream>
using namespace std;

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

int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;  // Tránh tràn số bằng cách chia trước
}

int main() {
    int a, b;
    cout << "Nhap hai so a va b: ";
    cin >> a >> b;
    cout << "LCM cua " << a << " va " << b << " la: " << lcm(a, b) << endl;
    return 0;
}

Bài tập áp dụng

Bài 1. Tính GCD và LCM của hai số

Mô tả: Cho hai số nguyên a và b. Tính GCD và LCM của chúng.
Yêu cầu: In ra GCD và LCM của a và b.
Ví dụ:

Input: 12 18
Output: GCD: 6, LCM: 36

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

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

int main() {
    int a, b;
    cout << "Nhap hai so a va b: ";
    cin >> a >> b;
    cout << "GCD: " << gcd(a, b) << ", LCM: " << lcm(a, b) << endl;
    return 0;
}

Bài 2. Kiểm tra dãy số nguyên tố cùng nhau

Mô tả: Cho một dãy số nguyên n phần tử. Kiểm tra xem tất cả các phần tử trong dãy có nguyên tố cùng nhau không (tức là GCD của dãy bằng 1).
Yêu cầu: Nếu GCD của dãy là 1, in YES, ngược lại in NO.
Ví dụ:

Input:

3
2 3 4
Output: YES

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int n, num, g;
    cout << "Nhap so luong phan tu: ";
    cin >> n;
    cout << "Nhap cac so: ";
    cin >> g;
    for (int i = 1; i < n; ++i) {
        cin >> num;
        g = gcd(g, num);
    }
    cout << (g == 1 ? "YES" : "NO") << endl;
    return 0;
}

Bài 3. Tính GCD và LCM của nhiều số

Mô tả: Cho dãy n số nguyên dương. Tính GCD và LCM của toàn bộ dãy.
Yêu cầu: In ra GCD và LCM của dãy.
Ví dụ:

Input:

4
6 9 12 15
Output: GCD: 3, LCM: 180

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

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

int main() {
    int n, num, result_gcd, result_lcm;
    cout << "Nhap so luong phan tu: ";
    cin >> n;
    cin >> result_gcd >> result_lcm;
    for (int i = 1; i < n; ++i) {
        cin >> num;
        result_gcd = gcd(result_gcd, num);
        result_lcm = lcm(result_lcm, num);
    }
    cout << "GCD: " << result_gcd << ", LCM: " << result_lcm << endl;
    return 0;
}

Bài 4. Tìm cặp số có GCD lớn nhất trong dãy

Mô tả: Nhập dãy n số nguyên dương. Tìm và in ra cặp số có GCD lớn nhất.
Yêu cầu: In ra cặp số và GCD lớn nhất.
Ví dụ:

Input:

5
8 16 4 12 24
Output: Cặp có GCD lớn nhất: (16, 24) với GCD: 8

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int n;
    cout << "Nhap so luong phan tu: ";
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; ++i) cin >> arr[i];
    
    int max_gcd = 0, x = 0, y = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int g = gcd(arr[i], arr[j]);
            if (g > max_gcd) {
                max_gcd = g;
                x = arr[i]; y = arr[j];
            }
        }
    }
    cout << "Cap co GCD lon nhat: (" << x << ", " << y << ") voi GCD: " << max_gcd << endl;
    return 0;
}

Bài 5. Rút gọn phân số

Mô tả: Cho phân số có tử số a và mẫu số b. Hãy rút gọn phân số về dạng tối giản.
Yêu cầu: In ra phân số tối giản.
Ví dụ:

Input: 8 12
Output: 2/3

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int a, b;
    cout << "Nhap tu so va mau so: ";
    cin >> a >> b;
    int g = gcd(a, b);
    cout << "Phan so toi gian: " << a / g << "/" << b / g << endl;
    return 0;
}

Bài 6. Kiểm tra hai số có nguyên tố cùng nhau không

Mô tả: Cho hai số nguyên a, b. Kiểm tra xem hai số này có nguyên tố cùng nhau không (GCD(a, b) = 1).
Yêu cầu: In YES nếu nguyên tố cùng nhau, ngược lại in NO.
Ví dụ:

Input: 5 9
Output: YES

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int a, b;
    cout << "Nhap hai so: ";
    cin >> a >> b;
    cout << (gcd(a, b) == 1 ? "YES" : "NO") << endl;
    return 0;
}

Bài 7. Tính chu kỳ lặp của hai sự kiện

Mô tả: Hai sự kiện diễn ra với chu kỳ lần lượt là a và b ngày. Tính số ngày để hai sự kiện xảy ra đồng thời.
Yêu cầu: In ra số ngày nhỏ nhất (LCM).
Ví dụ:

Input: 6 8
Output: 24

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

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

int main() {
    int a, b;
    cout << "Nhap chu ky hai su kien: ";
    cin >> a >> b;
    cout << "Chu ky lap dong thoi: " << lcm(a, b) << " ngay" << endl;
    return 0;
}

Bài 8. Bài toán bó đũa

Mô tả: Có n bó đũa, mỗi bó chứa số lượng đũa khác nhau. Tách tất cả bó thành bó nhỏ nhất sao cho số lượng đũa trong mỗi bó bằng nhau.
Yêu cầu: In số lượng đũa lớn nhất có thể trong mỗi bó (GCD).
Ví dụ:

Input:

3
6 9 15
Output: 3

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int n, num, result;
    cout << "Nhap so luong bo dua: ";
    cin >> n;
    cin >> result;
    for (int i = 1; i < n; ++i) {
        cin >> num;
        result = gcd(result, num);
    }
    cout << "So dua trong moi bo con: " << result << endl;
    return 0;
}

Bài 9. Bài toán sắp xếp lễ hội

Mô tả: Một lễ hội diễn ra mỗi a ngày và một hội chợ diễn ra mỗi b ngày. Tính số ngày để cả hai sự kiện cùng diễn ra.
Yêu cầu: In số ngày (LCM).
Ví dụ:

Input: 5 10
Output: 10

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

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

int main() {
    int a, b;
    cout << "Nhap chu ky le hoi va hoi cho: ";
    cin >> a >> b;
    cout << "Chu ky gap lai: " << lcm(a, b) << " ngay" << endl;
    return 0;
}

Bài 10. Đếm cặp số có GCD là 1

Mô tả: Cho dãy gồm n số nguyên dương. Đếm số cặp (a, b) sao cho GCD(a, b) = 1.
Yêu cầu: In ra số cặp thỏa mãn.
Ví dụ:

Input:

4
1 2 3 4
Output: 4

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int n, count = 0;
    cout << "Nhap so luong phan tu: ";
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; ++i) cin >> arr[i];
    
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (gcd(arr[i], arr[j]) == 1) count++;
        }
    }
    cout << "So cap co GCD bang 1: " << count << endl;
    return 0;
}

Đỗ Thành