Chương trình C++ tìm GCD của nhiều số (mảng)

Tìm GCD (Ước chung lớn nhất) của nhiều số (mảng). Sử dụng tính chất kết hợp: gcd(a,b,c) = gcd(gcd(a,b), c).

Thuật toán

gcd(a, b): // Euclidean algorithm
    if a == 0: return b
    return gcd(b % a, a)

getArrayGcd(arr, n):
    res = arr[0]
    for i = 1 to n-1:
        res = gcd(arr[i], res)
    return res
end

Code ví dụ

#include <iostream>
#include <vector>
#include <numeric> // C++17: std::gcd
using namespace std;

// Euclidean algorithm
int gcd(int a, int b) {
    if (a == 0) return b;
    return gcd(b % a, a);
}

int getArrayGcd(const vector<int>& arr) {
    if (arr.empty()) return 0;
    int res = arr[0];
    for(size_t i = 1; i < arr.size(); i++)
        res = gcd(arr[i], res);
    return res;
}

// C++17 version
int getArrayGcd17(const vector<int>& arr) {
    if (arr.empty()) return 0;
    int res = arr[0];
    for(size_t i = 1; i < arr.size(); i++)
        res = std::gcd(res, arr[i]);
    return res;
}

int main() {
    vector<int> arr = {4, 8, 16, 24};
    cout << "GCD cua mang: " << getArrayGcd(arr) << endl;
    
    // Test thêm
    vector<int> arr2 = {12, 18, 24, 36, 48};
    cout << "GCD cua {12,18,24,36,48}: " << getArrayGcd(arr2);
    return 0;
}

Kết quả

GCD cua mang: 4
GCD cua {12,18,24,36,48}: 6

Độ phức tạp

• GCD 2 số: O(log min(a,b)) - thuật toán Euclid.
• Mảng n số: O(n log M) với M là max giá trị.
• Không gian: O(1) thêm (không tính mảng đầu vào).

Mở rộng: LCM (Bội chung nhỏ nhất) của mảng

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b; // Tránh tràn: chia trước nhân sau
}

long long getArrayLcm(const vector<int>& arr) {
    long long res = arr[0];
    for(size_t i = 1; i < arr.size(); i++)
        res = lcm(res, arr[i]);
    return res;
}

Ứng dụng

• Rút gọn phân số.
• Tìm chu kỳ lặp (LCM).
• Toán học số, mật mã học.