Hiểu bài toán

Cho một mảng gồm n số nguyên dương a1, a2,..., an. Bài toán yêu cầu tìm giá trị lớn nhất của phép chia lấy dư a[x] % a[y] với các điều kiện: 1 ≤ x, y ≤ n và a[y] ≤ a[x]. Nói cách khác, ta cần tìm hai số trong mảng sao cho số bị chia lớn hơn hoặc bằng số chia, và hiệu số sau khi chia lấy dư là lớn nhất.

Dữ liệu:

• n ≤ 2×10⁵
• a[i] ≤ 10⁵⁶
• Max(a) / Min(a) ≤ 200,000 (đây là ràng buộc quan trọng cho giải thuật tối ưu).

Ví dụ: Input [3, 4, 5]. Các cặp thỏa mãn:

• 3%3=0, 3%4 (không hợp lệ vì 3<4), 3%5 (không hợp lệ)
• 4%3=1, 4%4=0, 4%5 (không hợp lệ)
• 5%3=2, 5%4=1, 5%5=0 Kết quả lớn nhất là 2.

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

Cách Brute Force

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

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

    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i] >= a[j]) {
                ans = max(ans, a[i] % a[j]);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Đây là cách tiếp cận trực tiếp nhất. Ta duyệt qua tất cả các cặp (i, j) trong mảng, kiểm tra xem a[i] có lớn hơn hoặc bằng a[j] không, nếu có thì tính a[i] % a[j] và cập nhật kết quả.

• Ưu điểm: Dễ hiểu, dễ cài đặt.
• Nhược điểm: Với n lên tới 2×10⁵, độ phức tạp O(n²) là không thể chấp nhận được (khoảng 4×10¹⁰ phép tính). Giải thuật này chỉ phù hợp cho các test dữ liệu nhỏ (n ≤ 2000).

Cách Optimized Iteration (Duyệt theo bội số)

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

const int MAX_A = 1000005;
int cnt[MAX_A]; // Mảng đánh dấu sự tồn tại và số lần xuất hiện

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    int max_val = 0;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        cnt[x]++;
        max_val = max(max_val, x);
    }

    // Tạo mảng prefix để tìm số lớn nhất <= k
    // pre[i] lưu số lớn nhất trong mảng input có giá trị <= i
    vector<int> pre(max_val * 2 + 2, 0);
    int last = 0;
    for (int i = 1; i <= max_val * 2 + 1; i++) {
        if (i <= max_val && cnt[i] > 0) last = i;
        pre[i] = last;
    }

    int ans = 0;
    // Duyệt qua từng số y có trong mảng
    for (int y = 1; y <= max_val; y++) {
        if (cnt[y] == 0) continue;

        // Duyệt các bội số của y: y, 2y, 3y...
        // Xem xét các số x trong khoảng [k*y, (k+1)*y - 1]
        // Số x lớn nhất có thể chia lấy dư là số lớn nhất trong mảng < (k+1)*y
        for (int k = 1; k * y <= max_val + y; k++) {
            int upper = (k + 1) * y - 1;
            if (upper > max_val) upper = max_val;

            // Tìm số lớn nhất <= upper
            int x = pre[upper];

            if (x >= k * y) {
                ans = max(ans, x % y);
            }
        }
    }

    cout << ans << endl;
    return 0;
}

• Time Complexity: O(maxval * log(maxval)) hoặc O(maxval * H(maxval))
• Space Complexity: O(max_val)

Giải thuật này dựa trên nhận định:

1. Nếu ta fix số chia là y, thì số dư r = x % y sẽ nằm trong khoảng [0, y-1]. Để r lớn nhất, x phải nằm gần một bội số của y nhưng không bằng bội đó.
2. Cụ thể, nếu x nằm trong khoảng [k*y, (k+1)*y - 1], thì x % y = x - k*y. Để maximize giá trị này, ta cần tìm số x lớn nhất trong mảng thuộc khoảng này.

Cách làm:

• Sắp xếp và loại bỏ trùng lặp hoặc dùng mảng đánh dấu (vì a[i] <= 10^6).
• Duyệt qua từng số y trong mảng.
• Với mỗi y, duyệt các bội số k*y. Với mỗi bội số, ta cần tìm số x lớn nhất trong mảng nằm trong khoảng [k*y, (k+1)*y - 1].
• Ta có thể dùng mảng pre (prefix maximum) để tra cứu nhanh số lớn nhất <= k*y - 1 (thực ra là (k+1)*y - 1).
• Do Max(a) / Min(a) ≤ 200000, số lần duyệt vòng lặp khá hạn chế. Ví dụ nếu y nhỏ, k lớn; nhưng nếu y lớn, k sẽ rất nhỏ. Tổng thể độ phức tạp chấp nhận được.

Cách Heuristic Optimization (Tối ưu hóa biên)

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());

    int m = a.size();
    int ans = 0;

    // Duyệt qua từng số y
    for (int i = 0; i < m; i++) {
        int y = a[i];
        // Nếu y <= ans, thì không thể tạo ra số dư > ans
        // (vì x % y < y)
        if (y <= ans) continue;

        // Duyệt các bội số: 2y, 3y...
        // Chỉ cần xét các x >= 2y. Nếu x < 2y, x % y = x - y < y.
        // Để x % y > ans, cần x > y + ans.
        // Thực tế, ta chỉ cần tìm x lớn nhất < 2y, x lớn nhất < 3y, ...

        for (int j = 1; j < m; j++) {
            // a[j] là candidate cho x
            if (a[j] < y) continue;

            // Tính số dư
            int rem = a[j] % y;
            if (rem > ans) ans = rem;

            // Heuristic: Nếu a[j] >= 2*y, ta có thể skip một số index
            // Tuy nhiên, giải pháp chuẩn là duyệt theo bội số của y
        }
    }
    return 0;
}

• Time Complexity: O(N log N + M * (MaxA / MinA)) ~ O(N log N + 200,000)
• Space Complexity: O(N)

Giải thuật này là phiên bản tối ưu hóa của phương pháp duyệt theo bội số.

1. Sắp xếp và loại trùng: Giúp truy cập nhanh và loại bỏ trường hợp bằng nhau.
2. Tối ưu hóa vòng lặp:
   • Với mỗi số chia y, ta chỉ quan tâm đến các số x lớn hơn y.
   • Để x % y lớn, x phải nằm trong khoảng [k*y + ans, (k+1)*y - 1] (nếu ans là giá trị hiện tại).
   • Tuy nhiên, cách làm hiệu quả nhất là duyệt các khoảng [k*y, (k+1)*y - 1].
   • Vì MaxA / MinA ≤ 200000, số lần lặp của k là khá nhỏ.
   • Trong mỗi khoảng, ta dùng upper_bound để tìm phần tử phù hợp.

Cải tiến chính:

• Chỉ duyệt k sao cho k*y <= max_val.
• Sử dụng upper_bound thay vì binary search tay để tìm phần tử trong mảng đã sort.
• Điều kiện dừng nhanh: Nếu y nhỏ hơn hoặc bằng ans hiện tại, ta có thể bỏ qua vì không thể tạo ra số dư lớn hơn y.

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

Bài học kinh nghiệm

• Bài toán có ràng buộc Max(a) / Min(a) ≤ 200,000. Đây là chìa khóa để chuyển từ O(N^2) sang O(N log N) hoặc O(MaxA log MaxA).
• Với mỗi số chia y, số dư x % y có giá trị tối đa là y - 1. Do đó, để tìm kết quả lớn nhất, ta ưu tiên các giá trị y lớn.
• Phép chia lấy dư lặp lại (x % y) có thể được tối ưu bằng cách xét các khoảng [ky, (k+1)y). X trong khoảng này có số dư x - k*y.
• Sử dụng mảng đánh dấu hoặc mảng precomputed prefix giúp tìm số lớn nhất trong một khoảng giá trị trong thời gian O(1) hoặc O(log N).

Lỗi thường gặp

• Quên xử lý trường hợp x = y (x % y = 0), điều này không ảnh hưởng đến giá trị lớn nhất nhưng cần logic đúng.
• Lỗi tràn số khi tính các bội số lớn (k*y) nếu không giới hạn biên.
• Sử dụng giải thuật O(N^2)导致 Timeout cho dữ liệu lớn.
• Bỏ qua việc loại bỏ trùng lặp (duplicate values). Nếu có nhiều số giống nhau, việc xử lý có thể sai hoặc chậm nếu không dùng set/sort unique.