Hiểu bài toán

Bài toán yêu cầu tìm ước chung lớn nhất (GCD) của một dãy số sau khi thay đổi đúng một phần tử bất kỳ trong dãy thành một số nguyên trong khoảng [1, 10^9]. Mục tiêu là tối đa hóa giá trị GCD này.

Đầu vào:

• n: Số lượng phần tử của dãy (1 ≤ n ≤ 10^6).
• a: Mảng gồm n số nguyên (1 ≤ a_i ≤ 10^6).

Đầu ra:

• Một số nguyên duy nhất là giá trị GCD lớn nhất có thể đạt được.

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

Cách Sử dụng mảng tiền tố và hậu tố (Prefix & Suffix GCD)

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

const int MAXN = 1e6 + 5;
int n;
int a[MAXN];
int pre[MAXN], suf[MAXN];

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

int main() {
    // Tối ưu tốc độ nhập xuất
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    // Tính GCD của tiền tố (từ trái sang phải)
    // pre[i] là GCD của a[1]...a[i]
    pre[0] = 0;
    for (int i = 1; i <= n; ++i) {
        pre[i] = gcd(pre[i - 1], a[i]);
    }

    // Tính GCD của hậu tố (từ phải sang trái)
    // suf[i] là GCD của a[i]...a[n]
    suf[n + 1] = 0;
    for (int i = n; i >= 1; --i) {
        suf[i] = gcd(suf[i + 1], a[i]);
    }

    long long res = 0;
    // Duyệt qua từng vị trí để loại bỏ phần tử tại đó
    for (int i = 1; i <= n; ++i) {
        // GCD khi loại bỏ a[i] là GCD của phần bên trái (pre[i-1]) và phần bên phải (suf[i+1])
        long long current_gcd = gcd(pre[i - 1], suf[i + 1]);
        res = max(res, current_gcd);
    }

    cout << res;
    return 0;
}

• Time Complexity: O(N) - Vòng lặp tính prefix, suffix và vòng lặp duyệt đều qua N phần tử.
• Space Complexity: O(N) - Cần mảng pre và suf kích thước N để lưu giá trị GCD.

Đây là phương pháp tối ưu nhất để giải quyết bài toán này. Ý tưởng chính là:

1. Xây dựng mảng pre (tiền tố GCD): pre[i] lưu GCD của a[1] đến a[i]. Điều này giúp tính nhanh GCD của bất kỳ đoạn đầu mảng nào.
2. Xây dựng mảng suf (hậu tố GCD): suf[i] lưu GCD của a[i] đến a[n]. Điều này giúp tính nhanh GCD của bất kỳ đoạn cuối mảng nào.
3. Khi ta muốn thay đổi một phần tử a[i], ta có thể coi như đang loại bỏ nó ra khỏi dãy (vì có thể thay thế nó bằng một số chia hết cho GCD còn lại của dãy). GCD của dãy còn lại khi loại bỏ a[i] chính là GCD của đoạn a[1]...a[i-1] và đoạn a[i+1]...a[n], tức là gcd(pre[i-1], suf[i+1]).
4. Ta duyệt qua tất cả các vị trí i từ 1 đến n, tính GCD tương ứng và cập nhật kết quả lớn nhất.

Cách Brute Force (Tối ưu hơn)

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

long long gcd(long long a, long long b) {
    while (b) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

int main() {
    int n;
    if (!(std::cin >> n)) return 0;

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

    long long max_gcd = 0;

    // Duyệt qua từng phần tử để loại bỏ
    for (int i = 0; i < n; ++i) {
        long long current_gcd = 0;
        // Tính GCD của các phần tử còn lại
        for (int j = 0; j < n; ++j) {
            if (i == j) continue;
            current_gcd = gcd(current_gcd, a[j]);
        }
        max_gcd = std::max(max_gcd, current_gcd);
    }

    std::cout << max_gcd << std::endl;
    return 0;
}

• Time Complexity: O(N^2 * log(max(A))) - Với N lên tới 10^6, cách này không thể chạy đúng giới hạn thời gian (quá chậm).
• Space Complexity: O(N) - Chỉ cần lưu mảng đầu vào.

Đây là cách tiếp cận trực quan nhất: với mỗi vị trí i, ta giả sử thay đổi phần tử tại đó. Sau đó, ta tính GCD của n-1 phần tử còn lại bằng cách lặp lại toàn bộ mảng.

Cách này đúng về mặt logic nhưng hiệu năng cực kỳ kém. Với n = 10^6, độ phức tạp O(n^2) là không thể chấp nhận được. Tuy nhiên, nó có thể được dùng cho các bài toán với n nhỏ (ví dụ n <= 1000 hoặc n <= 10^4).

Nó cho thấy tầm quan trọng của việc tối ưu hóa tính toán GCD lặp lại bằng cách sử dụng cấu trúc dữ liệu phụ trợ như trong Approach 1.

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

Bài học kinh nghiệm

• Bài toán có thể biến đổi thành: Tìm GCD lớn nhất của toàn bộ dãy khi loại bỏ một phần tử bất kỳ.
• Sử dụng mảng tiền tố (Prefix GCD) và hậu tố (Suffix GCD) để tính toán GCD của các đoạn con trong thời gian O(1) sau khi đã xử lý trước O(N).
• Khi loại bỏ phần tử a[i], GCD của phần còn lại là gcd(GCD(a[1]...a[i-1]), GCD(a[i+1]...a[n])).

Lỗi thường gặp

• Lỗi chỉ số mảng (Off-by-one error): Khi tính GCD của các phần tử bên trái i là pre[i-1] và bên phải là suf[i+1]. Cần chú ý xử lý biên (khi i=1 hoặc i=n).
• Sử dụng biến sai kiểu: GCD có thể tăng nhanh, nên dùng long long để tránh tràn số nếu a_i lớn, mặc dù đề bài cho a_i <= 10^6.
• Quên tối ưu hóa I/O: Với n lớn (10^6), việc nhập xuất cơ bản có thể chậm. Nên dùng ios_base::sync_with_stdio(0); cin.tie(0); trong C++.