Tìm ƯCLN của n số nguyên

29
Lập trình C++

Bài toán: Cho dãy số nguyên với n phần tử (n <= 106). Tìm ước chung lớn nhất của n số nguyên

Với bài toán này, bạn có thể tham khảo code sau đây:

#include <iostream>
using namespace std;
int uc(int a, int b) {
    if(a == 0 || b == 0) { return a;}
    while (a!=b){
        if (a > b) {a -= b;}
        else {b -= a;}
    }
    return a;
}
int UCLN(int a[], int n) {
    if (n == 1) return a[0];
    else return uc(a[n-1],UCLN(a, n-1));
}
int main() {
    freopen("GCD.INP","r",stdin);
    freopen("GCD.OUT","w",stdout);
    int n, a[1000];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cout << UCLN (a, n);
    return 0;
}

Cách 2: Chúng ta có thể sử dụng vòng lặp để xác định UCLN của n số nguyên. Tham khảo:

#include <iostream>
using namespace std;
int uc(int a, int b) {
    if(a == 0 || b == 0) { return a;}
    while (a!=b){
        if (a > b) {a -= b;}
        else {b -= a;}
    }
    return a;
}
int UCLN(int a[], int n) {
    int u = a[0];
    for (int i = 0; i < n; i++) {
        u = uc(u, a[i]);
    }
    return u;
}
int main() {
    freopen("GCD.INP","r",stdin);
    freopen("GCD.OUT","w",stdout);
    int n, a[1000];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cout << UCLN (a, n);
    return 0;
}