Hiểu bài toán

Bài toán yêu cầu tìm ước chung lớn nhất (UCLN) lớn nhất có thể giữa hai phần tử bất kỳ trong dãy số cho trước. Tuy nhiên, lời giải và ví dụ cho thấy bài toán thực chất chỉ yêu cầu tìm UCLN lớn nhất giữa hai phần tử KỀ NHAU trong dãy (tức là tìm max(gcd(ai, a{i+1})) với mọi i từ 1 đến n-1).

Các cách tiếp cận

Cách Brute Force (Duyệt kép)

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

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

int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int max_gcd = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            max_gcd = max(max_gcd, gcd(a[i], a[j]));
        }
    }
    cout << max_gcd;
    return 0;
}

• Time Complexity: O(n^2 log M)
• Space Complexity: O(n)

Phương pháp này duyệt qua tất cả các cặp phần tử (i, j) trong dãy, tính UCLN của mỗi cặp và tìm giá trị lớn nhất. Tuy nhiên, đây không phải là lời giải được chấp nhận trong các nộp bài do độ phức tạp quá cao. Lời giải này chỉ minh họa cho bài toán tổng quát hơn (tìm UCLN lớn nhất giữa bất kỳ hai phần tử nào).

Cách Duyệt đơn (Adjacent Pairs)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    int max_gcd = 0;
    for(int i = 0; i < n - 1; i++) {
        int g = __gcd(a[i], a[i+1]);
        max_gcd = max(max_gcd, g);
    }

    cout << max_gcd << "\n";
    return 0;
}

• Time Complexity: O(n log M)
• Space Complexity: O(n)

Đây là lời giải chính xác cho bài toán đã cho. Thay vì duyệt tất cả các cặp, ta chỉ cần duyệt qua các cặp kề nhau (a[i], a[i+1]). Với mỗi cặp, ta tính UCLN bằng hàm có sẵn (_gcd) hoặc tự implement. Độ phức tạp là O(n log M) với M là giá trị lớn nhất của phần tử. Hàm _gcd trong C++ dùng thuật toán Euclid.

Cách Tối ưu với hàm tự implement

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

int UCLN(int a, int b) {
    while (b > 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    freopen("ucln.inp", "r", stdin);
    freopen("ucln.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    int a[1005];
    for(int i = 1; i <= n; i++) cin >> a[i];

    int sct = 0;
    for(int i = 2; i <= n; i++) {
        sct = max(sct, UCLN(a[i], a[i-1]));
    }
    cout << sct;
    return 0;
}

• Time Complexity: O(n log M)
• Space Complexity: O(n)

Cách tiếp cận tương tự như trên nhưng sử dụng hàm UCLN tự implement thay vì dùng thư viện. Phiên bản này cũng sử dụng mảng tĩnh (int a[1005]) thay vì vector và có thêm các tối ưu hóa I/O như freopen và iosbase::syncwith_stdio(0). Đây là cách tiếp cận an toàn hơn trong các kỳ thi lập trình cạnh tranh khi không chắc chắn về thư viện.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán chỉ yêu cầu kiểm tra các cặp phần tử kề nhau, không cần kiểm tra tất cả các cặp.
• UCLN có thể tính bằng thuật toán Euclid (a % b) với độ phức tạp logarithmic.
• Các tối ưu hóa I/O (freopen, syncwithstdio) giúp giảm thời gian chạy đáng kể trong các bài toán lớn.

Lỗi thường gặp

• Lầm tưởng bài toán yêu cầu tìm UCLN lớn nhất giữa BẤT KỲ hai phần tử nào trong dãy (sẽ cần O(n^2) và không hiệu quả).
• Quên kiểm tra trường hợp n=1 (không có cặp nào để so sánh).
• Sử dụng mảng có kích thước cố định nhỏ hơn giới hạn của đề bài.