Hướng dẫn giải của Mảng GCD

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, sussyboy, nguyenquangteok8

Hiểu bài toán

Cho một mảng A gồm n phần tử. Tìm mảng con liên tiếp (l, r) sao cho GCD của tất cả các phần tử trong mảng con đó bằng 1, và độ dài (r - l + 1) là ngắn nhất có thể. Nếu có nhiều mảng con cùng độ dài ngắn nhất, chọn mảng có l nhỏ nhất. Nếu không tồn tại mảng con nào thỏa mãn, xuất -1.

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

Cách Brute Force (Tối ưu hóa)

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

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

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

    int min_len = n + 1;
    int best_l = -1, best_r = -1;

    for (int i = 0; i < n; i++) {
        int current_gcd = a[i];
        for (int j = i; j < n; j++) {
            current_gcd = gcd(current_gcd, a[j]);
            if (current_gcd == 1) {
                int len = j - i + 1;
                if (len < min_len) {
                    min_len = len;
                    best_l = i + 1;
                    best_r = j + 1;
                }
                break; // Optimization: found shortest for this start
            }
        }
    }

    if (min_len == n + 1) {
        cout << -1 << endl;
    } else {
        cout << min_len << " " << best_l << " " << best_r << endl;
    }
    return 0;
}

Time Complexity: O(n^2) trong trường hợp xấu nhất (nếu không có đoạn GCD=1), nhưng với các test thực tế hoặc do tính chất GCD giảm nhanh, nó thường chạy nhanh hơn.
Space Complexity: O(1)

Cách tiếp cận này thử tất cả các vị trí bắt đầu i. Với mỗi i, nó duyệt qua các vị trí kết thúc j từ i trở đi, cập nhật GCD của đoạn A[i...j]. Nếu GCD bằng 1, ta đã tìm được đoạn ngắn nhất bắt đầu tại i (vì GCD không thể tăng lên sau khi bằng 1), nên có thể break và sang i tiếp theo. Tuy nhiên, độ phức tạp có thể lên tới O(n^2) nếu không có đoạn nào có GCD=1.

Cách Duyệt theo các giá trị GCD (GCD Grouping)

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

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

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

    // Danh sách các cặp (GCD, vị trí bắt đầu) cho đoạn kết thúc tại i-1
    vector<pair<int, int>> prev_groups;

    int min_len = n + 1;
    int best_l = -1, best_r = -1;

    for (int i = 0; i < n; i++) {
        vector<pair<int, int>> curr_groups;
        // Thêm phần tử hiện tại
        curr_groups.push_back({a[i], i});

        // Kết hợp với các nhóm trước đó
        for (auto p : prev_groups) {
            int g = __gcd(p.first, a[i]);
            // Chỉ thêm vào nếu GCD khác với nhóm cuối cùng (tránh trùng lặp)
            // Quan trọng: Giữ lại vị trí bắt đầu nhỏ nhất cho mỗi GCD
            if (curr_groups.back().first != g) {
                curr_groups.push_back({g, p.second});
            }
        }

        // Kiểm tra xem có đoạn nào GCD=1 không
        for (auto p : curr_groups) {
            if (p.first == 1) {
                int len = i - p.second + 1;
                if (len < min_len) {
                    min_len = len;
                    best_l = p.second + 1;
                    best_r = i + 1;
                }
            }
        }

        prev_groups = curr_groups;
    }

    if (min_len == n + 1) {
        cout << -1 << endl;
    } else {
        cout << min_len << " " << best_l << " " << best_r << endl;
    }
    return 0;
}

Time Complexity: O(n log A_max)
Space Complexity: O(log A_max)

Đây là phương pháp tối ưu hóa O(n^2) bằng cách nhận thấy rằng số lượng các giá trị GCD khác nhau của các mảng con liên tiếp ending tại một vị trí là rất ít (khoảng O(log A_max)). Với mỗi vị trí i, ta duy trì một danh sách các cặp (GCD, vị trí bắt đầu). Danh sách này được cập nhật từ danh sách của i-1 bằng cách tính GCD với A[i]. Nếu GCD mới bằng GCD cũ của nhóm cuối cùng, ta hợp nhất chúng (giữ lại vị trí bắt đầu nhỏ nhất). Cuối cùng, ta chỉ cần kiểm tra các cặp trong danh sách hiện tại có GCD bằng 1 hay không.

Cách Binary Search + Segment Tree (hoặc Sparse Table)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// Segment Tree để truy vấn GCD trong đoạn [l, r]
class SegTree {
    int n;
    vector<int> tree;
public:
    SegTree(const vector<int>& arr) {
        n = arr.size();
        tree.resize(4 * n);
        build(arr, 1, 0, n - 1);
    }

    void build(const vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, node * 2, start, mid);
            build(arr, node * 2 + 1, mid + 1, end);
            tree[node] = gcd(tree[node * 2], tree[node * 2 + 1]);
        }
    }

    int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0;
        if (l <= start && end <= r) return tree[node];
        int mid = (start + end) / 2;
        return gcd(query(node * 2, start, mid, l, r), 
                   query(node * 2 + 1, mid + 1, end, l, r));
    }

    int query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
};

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

    int n;
    cin >> n;
    vector<int> a(n);
    bool has_one = false;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] == 1) has_one = true;
    }

    // Optimization: Nếu có số 1, đáp án luôn là 1
    if (has_one) {
        for(int i=0; i<n; i++) {
            if(a[i] == 1) {
                cout << "1 " << i+1 << " " << i+1 << endl;
                return 0;
            }
        }
    }

    SegTree st(a);

    int min_len = n + 1;
    int best_l = -1, best_r = -1;

    for (int i = 0; i < n; i++) {
        // Optimization: Nếu a[i] chia hết cho min_len hiện tại, 
        // không thể tìm được đoạn ngắn hơn bắt đầu tại i.
        if (min_len != n + 1 && min_len <= n - i) {
             // Thêm logic prune nếu cần, nhưng Binary Search là chính
        }

        // Binary Search độ dài
        int low = 1, high = n - i;
        int current_ans = -1;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (st.query(i, i + mid - 1) == 1) {
                current_ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        if (current_ans != -1) {
            if (current_ans < min_len) {
                min_len = current_ans;
                best_l = i + 1;
                best_r = i + current_ans;
            }
        }
    }

    if (min_len == n + 1) {
        cout << -1 << endl;
    } else {
        cout << min_len << " " << best_l << " " << best_r << endl;
    }
    return 0;
}

Time Complexity: O(n log^2 n) hoặc O(n log n log A_max) tùy thuộc vào cách implement Segment Tree (nếu query O(1) dùng Sparse Table thì O(n log n)). Ở đây dùng Segment Tree query O(log n) và Binary Search O(log n) nên là O(n log^2 n).
Space Complexity: O(n)

Với mỗi vị trí bắt đầu i, ta muốn tìm độ dài k nhỏ nhất sao cho GCD(A[i...i+k-1]) = 1. Hàm GCD là hàm đơn điệu (nếu thêm phần tử, GCD có thể giảm hoặc giữ nguyên, không tăng). Do đó, ta có thể dùng Binary Search để tìm độ dài k này. Để kiểm tra GCD của đoạn nhanh chóng, ta dùng Segment Tree hoặc Sparse Table (cần precompute).

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

Cách tiếp cận	Time	Space	Tên
1	O(n^2) trong trường hợp xấu nhất (nếu không có đoạn GCD=1), nhưng với các test thực tế hoặc do tính chất GCD giảm nhanh, nó thường chạy nhanh hơn.	O(1)	Brute Force (Tối ưu hóa)
2	O(n log A_max)	O(log A_max)	Duyệt theo các giá trị GCD (GCD Grouping)
3	O(n log^2 n) hoặc O(n log n log A_max) tùy thuộc vào cách implement Segment Tree (nếu query O(1) dùng Sparse Table thì O(n log n)). Ở đây dùng Segment Tree query O(log n) và Binary Search O(log n) nên là O(n log^2 n).	O(n)	Binary Search + Segment Tree (hoặc Sparse Table)

Bài học kinh nghiệm

GCD của một đoạn con chỉ có thể giảm dần khi thêm phần tử vào, và số lượng các giá trị GCD khác nhau của các đoạn con ending tại một vị trí là rất nhỏ (O(log A_max)).
Nếu mảng chứa số 1, đáp án luôn là độ dài 1 (chính số 1 đó).
Nếu không có số 1, độ dài ngắn nhất có thể tìm được là 2 (nếu có 2 số nguyên tố cùng nhau).

Lỗi thường gặp

Quên xử lý trường hợp mảng không chứa số 1 và không có đoạn GCD=1 nào -> xuất -1.
Sai quy luật monotonicity khi dùng Binary Search (cần đảm bảo tính chất: nếu đoạn dài có GCD=1, đoạn ngắn hơn chưa chắc có GCD=1, nhưng nếu đoạn dài không có GCD=1 thì đoạn dài hơn chắc chắn không có GCD=1? Không, GCD có thể giảm xuống 1 ở đoạn dài hơn. Tuy nhiên, ta đang tìm độ dài ngắn nhất cho mỗi điểm bắt đầu, nên Binary Search tìm độ dài k sao cho GCD(i, i+k-1) == 1. Hàm f(k) = GCD(i, i+k-1) là đơn điệu giảm, nhưng f(k)==1 không đơn điệu với k (nó có thể bằng 1 ở k nhỏ, rồi không bằng 1 ở k lớn hơn, rồi lại bằng 1 ở k lớn nhất). Tuy nhiên, ta đang tìm k nhỏ nhất thỏa mãn f(k)==1. Binary Search chỉ hiệu quả nếu ta tìm k lớn nhất thỏa mãn điều kiện hoặc nếu hàm đơn điệu. Ở đây, ta cần kiểm tra xem đoạn [i, j] có GCD=1 hay không. Nếu dùng Binary Search để tìm j nhỏ nhất sao cho GCD=1, ta cần lưu ý: GCD giảm dần, nhưng việc GCD bằng 1 ở một đoạn dài không đảm bảo đoạn ngắn hơn cũng bằng 1. Ví dụ: [2, 3, 2] -> GCD(2,3)=1 (độ dài 2), GCD(2,3,2)=1 (độ dài 3). Nếu ta thử độ dài 3 thấy bằng 1, ta không thể kết luận độ dài 2 hay 1 bằng 1. Do đó Binary Search tìm độ dài ngắn nhất không trực tiếp áp dụng được trừ khi ta dùng phương pháp khác như Segment Tree kết hợp duyệt từ trái sang phải.
Trong solution GCD Grouping, nếu không loại bỏ các GCD trùng lặp (ví dụ cùng GCD nhưng vị trí bắt đầu khác nhau, ta chỉ cần giữ vị trí bắt đầu nhỏ nhất), danh sách có thể phình to không cần thiết.

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.