Hiểu bài toán

Cho một dãy gồm N số nguyên dương. Nhiệm vụ của bạn là tìm độ dài dãy con liên tiếp dài nhất sao cho bất kỳ hai số nguyên tố cùng nhau (GCD = 1) ở bất kỳ cặp phần tử liền kề nào trong dãy con đó. Nói cách khác, cần tìm đoạn liên tiếp dài nhất trong dãy mà tại đó cặp phần tử kề nhau đều nguyên tố cùng nhau.

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

Cách Duyệt đơn (One-pass)

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

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

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

    // Xử lý file input/output
    ifstream fin("COPRIME.INP");
    ofstream fout("COPRIME.OUT");

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

    int maxLen = 0;
    int currentLen = 1; // Bắt đầu với 1 phần tử

    // Duyệt từ phần tử thứ 2 trở đi
    for(int i = 1; i < N; i++) {
        if(gcd(a[i], a[i-1]) == 1) {
            currentLen++; // Mở rộng đoạn liên tiếp
            maxLen = max(maxLen, currentLen);
        } else {
            currentLen = 1; // Reset lại độ dài, bắt đầu từ phần tử hiện tại
        }
    }

    // Theo đề bài, dãy phải có độ dài >= 2
    if(maxLen < 2) maxLen = 0;

    fout << maxLen << "\n";
    fin.close();
    fout.close();
    return 0;
}

• Time Complexity: O(N * log(V)) (V là giá trị phần tử lớn nhất)
• Space Complexity: O(N)

Đây là cách tiếp cận trực quan và hiệu quả nhất. Ta duyệt qua mảng một lần duy nhất. Biến currentLen lưu độ dài đoạn liên tiếp thỏa mãn điều kiện đang xét. Nếu gcd(a[i], a[i-1]) == 1, ta mở rộng đoạn hiện tại (currentLen++). Ngược lại, ta cập nhật độ dài lớn nhất tìm được (maxLen) và reset currentLen về 1 để bắt đầu một đoạn mới từ phần tử hiện tại. Độ phức tạp thời gian là O(N) với mỗi lần tính GCD mất O(log(min(a[i], a[i-1]))).

Cách Quy hoạch động (Đơn giản hóa)

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

int main() {
    if (fopen("coprime.inp","r")) {
        freopen("coprime.inp","r",stdin);
        freopen("coprime.out","w",stdout);
    }

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

    int ans = 0;
    int cur = 1;

    for (int i = 1; i < n; i++) {
        if (__gcd(a[i], a[i - 1]) == 1)
            cur++;
        else {
            if (cur >= 2) ans = max(ans, cur);
            cur = 1;
        }
    }
    if (cur >= 2) ans = max(ans, cur);

    cout << ans;
    return 0;
}

• Time Complexity: O(N * log(V))
• Space Complexity: O(N)

Cách tiếp cận này về cơ bản giống cách 1 nhưng logic cập nhật ans được thực hiện ngay tại thời điểm đoạn thỏa mãn bị ngắt hoặc cuối vòng lặp. Nó sử dụng hàm __gcd có sẵn trong C++ để kiểm tra tính nguyên tố cùng nhau. Biến cur đóng vai trò như currentLen và ans như maxLen. Logic xử lý khá giống nhau, chỉ khác biệt nhỏ về thời điểm gán giá trị.

Cách Quy hoạch động (Chi tiết)

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

int kt(int a, int b) {
    int k = __gcd(a, b);
    if (k == 1) return 1;
    else return 0;
}

int main() {
    if(fopen("coprime.inp","r")) {
        freopen("coprime.inp","r",stdin);
        freopen("coprime.out","w",stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    int n;
    cin >> n;
    int arr[n+1];
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    int l = 0, d = 1, ans = 1;
    for (int i = 0; i < n - 1; i++)
        if (kt(arr[i], arr[i+1])) d++;
        else {
            ans = max(ans, d);
            d = 1;
        }
    ans = max(ans, d);

    if (ans != 1) cout << ans;
    else cout << 0;
    return 0;
}

• Time Complexity: O(N * log(V))
• Space Complexity: O(N)

Cách tiếp cận này cũng sử dụng thuật toán quy hoạch động tương tự. Biến d (độ dài) được khởi tạo bằng 1. Trong vòng lặp for từ 0 đến n-2, nó kiểm tra cặp (arr[i], arr[i+1]). Nếu nguyên tố cùng nhau, d tăng lên. Nếu không, nó cập nhật ans và reset d. Cuối cùng, so sánh ans với d một lần nữa để xử lý đoạn cuối cùng. Nếu kết quả chỉ là 1 (tức chỉ có 1 phần tử) thì in ra 0 theo yêu cầu đề bài.

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

Bài học kinh nghiệm

• Vấn đề có thể được giải quyết bằng cách duyệt đơn (one-pass) với độ phức tạp tuyến tính O(N), vì ta chỉ quan tâm đến mối quan hệ giữa các cặp phần tử liền kề.
• Biến lưu trữ độ dài đoạn liên tiếp hiện tại (currentLen) phải được khởi tạo đúng giá trị ban đầu (1) và xử lý cẩn thận ở các bước đầu và cuối của mảng.
• Sử dụng hàm GCD có sẵn (__gcd hoặc hàm tự viết) là chìa khóa để kiểm tra điều kiện 'nguyên tố cùng nhau'.

Lỗi thường gặp

• Quên kiểm tra điều kiện độ dài dãy con phải lớn hơn hoặc bằng 2. Nếu chỉ tìm được đoạn dài 1, đáp án phải là 0.
• Lỗi truy cập ngoài biên mảng khi duyệt cặp phần tử liền kề (ví dụ: vòng lặp chạy tới i < n thay vì i < n-1 hoặc i < n).
• Không xử lý đúng trường hợp dãy chỉ toàn các cặp không nguyên tố cùng nhau, dẫn đến maxLen không được cập nhật chính xác.