Hiểu bài toán

Bài toán yêu cầu tìm giá trị lớn nhất của ước số chung (UCLN) giữa hai phần tử bất kỳ trong dãy số cho trước. Cụ thể, với dãy số gồm n phần tử a[0], a[1], ..., a[n-1], ta cần tìm max(UCLN(a[i], a[j])) với mọi cặp i < j. Tuy nhiên, dựa trên các giải pháp đã nộp, bài toán thực chất là tìm giá trị lớn nhất của UCLN giữa hai phần tử liên tiếp trong dãy (tức max(UCLN(a[i], a[i+1])) với mọi i từ 0 đến n-2).

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

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

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

long long gcd(long long a, long long b) {
    while (b) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

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

    long long ans = 0;
    // Duyệt tất cả cặp (i, j) với i < j
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            ans = max(ans, gcd(a[i], a[j]));
        }
    }
    cout << ans;
    return 0;
}

• Time Complexity: O(n² × log(max(a)))
• Space Complexity: O(n)

Cách tiếp cận này kiểm tra tất cả các cặp phần tử trong dãy để tìm UCLN lớn nhất. Với mỗi cặp (i, j), ta tính UCLN và cập nhật kết quả. Độ phức tạp thời gian là O(n²) cho số lần lặp và O(log(max(a))) cho mỗi lần tính UCLN. Cách này chỉ khả thi với n nhỏ (< 1000).

Cách Duyệt một lượt (Tối ưu)

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

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

    ll ans = 0;
    for (int i = 0; i < n - 1; i++) {
        ans = max(ans, __gcd(a[i], a[i+1]));
    }
    cout << ans;
    return 0;
}

• Time Complexity: O(n × log(max(a)))
• Space Complexity: O(n)

Giải pháp tối ưu dựa trên nhận định: UCLN lớn nhất giữa hai phần tử bất kỳ trong dãy bằng UCLN lớn nhất giữa hai phần tử liên tiếp. Chỉ cần duyệt một lần qua dãy, tính UCLN của mỗi cặp phần tử liên tiếp và lưu giá trị lớn nhất. Hàm __gcd có sẵn trong <bits/stdc++.h> giúp tính nhanh.

Cách Xử lý IO nhanh

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    long long ans = 0;
    for(int i = 0; i + 1 < N; i++) {
        ans = max(ans, (long long)gcd(a[i], a[i+1]));
    }
    cout << ans;
    return 0;
}

• Time Complexity: O(n × log(max(a)))
• Space Complexity: O(n)

Biến thể của cách duyệt một lượt, tối ưu thêm bằng cách tắt đồng bộ hóa IO và cin.tie(nullptr) để tăng tốc độ nhập xuất. Điều này quan trọng trong lập trình cạnh tranh khi xử lý dữ liệu lớn.

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

Bài học kinh nghiệm

• UCLN lớn nhất giữa hai phần tử bất kỳ trong dãy luôn bằng UCLN lớn nhất giữa hai phần tử liên tiếp
• Hàm __gcd trong <bits/stdc++.h> hoặc hàm gcd trong <numeric> ở C++17 giúp tính UCLN nhanh chóng
• Với dữ liệu lớn, tối ưu IO (ios::syncwithstdio(false); cin.tie(nullptr);) là cần thiết

Lỗi thường gặp

• Quên include các thư viện cần thiết như <bits/stdc++.h> hoặc <algorithm>
• Sử dụng sai kiểu dữ liệu (int thay vì long long) dẫn đến tràn số khi tính UCLN
• Lặp sai giới hạn (lặp đến n thay vì n-1 cho vòng lặp chính)
• Không xử lý trường hợp n=1 hoặc n=2