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;
}