Hiểu bài toán

Cho một dãy số A gồm N số nguyên dương. Nhiệm vụ của bạn là tìm một số nguyên dương K và một chỉ số i (1 ≤ i ≤ N) sao cho:

1. K là ước chung lớn nhất của tất cả các phần tử trong dãy A khi loại bỏ phần tử A[i] (tức là GCD của các phần tử còn lại).
2. K phải lớn hơn GCD của toàn bộ dãy A. Nếu có nhiều đáp án, chọn chỉ số i nhỏ nhất. Nếu không tồn tại đáp án, in ra -1.

Tóm tắt yêu cầu:

• Tính GCD của toàn bộ dãy A (gọi là G_all).
• Với mỗi vị trí i, tính GCD của tất cả các phần tử ngoại trừ A[i] (gọi là G_i).
• Tìm Gi lớn nhất thỏa mãn Gi > G_all.
• In ra chỉ số i nhỏ nhất tìm được và giá trị G_i tương ứng. Nếu không có, in -1.

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

Cách Prefix và Suffix GCD

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

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

    // Tính GCD tất cả các phần tử
    long long g_all = 0;
    for (int i = 1; i <= n; i++) {
        g_all = __gcd(g_all, a[i]);
    }

    // Tính Prefix GCD: dp1[i] là GCD của a[1]...a[i]
    vector<long long> dp1(n + 2, 0);
    for (int i = 1; i <= n; i++) {
        dp1[i] = __gcd(dp1[i - 1], a[i]);
    }

    // Tính Suffix GCD: dp2[i] là GCD của a[i]...a[n]
    vector<long long> dp2(n + 2, 0);
    for (int i = n; i >= 1; i--) {
        dp2[i] = __gcd(dp2[i + 1], a[i]);
    }

    long long max_k = -1;
    int best_idx = -1;

    // Duyệt qua mỗi vị trí i, loại bỏ a[i]
    // GCD còn lại là GCD(dp1[i-1], dp2[i+1])
    for (int i = 1; i <= n; i++) {
        long long g_remove_i = __gcd(dp1[i - 1], dp2[i + 1]);
        if (g_remove_i > g_all) {
            if (g_remove_i > max_k) {
                max_k = g_remove_i;
                best_idx = i;
            }
        }
    }

    if (best_idx == -1) {
        cout << -1 << endl;
    } else {
        cout << best_idx << " " << max_k << endl;
    }

    return 0;
}

• Time Complexity: O(N * log(max(A)))
• Space Complexity: O(N)

Đây là phương pháp tối ưu hóa của brute force. Thay vì tính lại GCD từ đầu mỗi khi loại bỏ một phần tử (tốn O(N)), ta sử dụng hai mảng truy tố:

1. dp1[i]: GCD của các phần tử từ đầu đến i.
2. dp2[i]: GCD của các phần tử từ i đến cuối. Khi loại bỏ a[i], GCD của dãy còn lại chính là GCD của dp1[i-1] (phần bên trái) và dp2[i+1] (phần bên phải). Thao tác này chỉ mất O(log(max(A))) cho mỗi i.

• Bước 1: Tính GCD toàn bộ dãy để so sánh.
• Bước 2: Xây dựng mảng Prefix và Suffix.
• Bước 3: Duyệt qua từng chỉ số, tính GCD còn lại và cập nhật kết quả nếu thỏa điều kiện. Độ phức tạp tổng quan là O(N * log(max(A))) về thời gian và O(N) về bộ nhớ.

Cách Brute Force (Tính lại toàn bộ)

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

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

    long long g_all = 0;
    for (int i = 1; i <= n; i++) {
        g_all = __gcd(g_all, a[i]);
    }

    long long max_k = -1;
    int best_idx = -1;

    for (int i = 1; i <= n; i++) {
        long long g_remove_i = 0;
        // Tính GCD của dãy khi bỏ a[i]
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            g_remove_i = __gcd(g_remove_i, a[j]);
        }

        if (g_remove_i > g_all) {
            if (g_remove_i > max_k) {
                max_k = g_remove_i;
                best_idx = i;
            }
        }
    }

    if (best_idx == -1) {
        cout << -1 << endl;
    } else {
        cout << best_idx << " " << max_k << endl;
    }

    return 0;
}

• Time Complexity: O(N^2 * log(max(A)))
• Space Complexity: O(N)

Đây là cách tiếp cận trực quan nhất.

• Bước 1: Tính GCD của toàn bộ dãy.
• Bước 2: Với mỗi chỉ số i từ 1 đến N:
  • Khởi tạo biến g_temp = 0.
  • Duyệt qua các chỉ số j từ 1 đến N, nếu j != i thì cập nhật g_temp = gcd(g_temp, a[j]).
  • So sánh g_temp với GCD toàn dãy và cập nhật kết quả. Phương pháp này chậm và chỉ phù hợp với N nhỏ (ví dụ N ≤ 1000). Với N lớn (10^5), nó chắc chắn bị TLE.

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

Bài học kinh nghiệm

• GCD(a, b, c) = GCD(GCD(a, b), c). Tính chất kết hợp này cho phép chia dãy thành các phần để tính toán riêng biệt.
• Việc loại bỏ một phần tử tại vị trí i chia dãy thành 2 phần độc lập (trước i và sau i). GCD của phần còn lại là GCD của GCD hai phần này.
• Nếu GCD của toàn bộ dãy là G, thì mọi GCD con của dãy đều là bội của G. Để tìm GCD lớn hơn G, ta cần tìm cách làm trội hơn GCD hiện tại.

Lỗi thường gặp

• Xử lý sai trường hợp biên: Khi i là phần tử đầu tiên (i=1) hoặc cuối cùng (i=N), một trong hai phần Prefix hoặc Suffix rỗng. GCD của một phần rỗng là 0, nhưng gcd(0, x) = x nên cách tính gcd(dp1[i-1], dp2[i+1]) vẫn đúng.
• Nếu không có chỉ số i nào thỏa mãn điều kiện (tức là GCD sau khi loại bỏ phần tử nào cũng không lớn hơn GCD toàn dãy), cần in ra -1 theo yêu cầu đề bài.
• Sử dụng biến kiểu int cho các số lớn có thể gây tràn số (overflow). Nên dùng long long cho các giá trị GCD và phần tử.