Tóm tắt đề bài

Cho dãy \(A\) gồm \(n\) số nguyên dương (\(n \le 10^6\)), và số \(k\). Gọi \(d(x)\) là số lượng ước của \(x\). Ta cần tìm độ dài đoạn con ngắn nhất sao cho trong đoạn con đó có ít nhất \(k\) phần tử mà mỗi phần tử thuộc nhóm có \(d(a_i)\) lớn nhất trong toàn dãy. Nếu trong cả dãy có ít hơn \(k\) phần tử như vậy thì in \(-1\).

Phân tích

• Ta cần biết giá trị lớn nhất của \(d(a_i)\) trên toàn dãy, gọi là \(D_{\max}\).
• Các vị trí “tốt” là những \(i\) thỏa \(d(a_i) = D_{\max}\).
• Bài toán sau đó trở thành:
  • Cho một dãy nhị phân theo vị trí (tốt/không tốt), hãy tìm đoạn con ngắn nhất chứa ít nhất \(k\) vị trí tốt.
• Nút thắt là tính \(d(a_i)\) với \(a_i \le 10^7\), \(n\) tới \(10^6\):
  • Không thể phân tích từng số bằng thử chia tới \(\sqrt{a_i}\) (quá chậm).
  • Cần tiền xử lý nhanh kiểu sàng.

Nhận xét quan trọng

• Vì chỉ cần \(d(a_i)\) cho các giá trị xuất hiện trong mảng, ta có thể:
  • Tính ước đếm cho mọi số từ \(1\) đến \(M = \max(a_i)\) bằng “sàng đếm ước”:
    • Với mỗi \(i\), cộng 1 vào tất cả bội số của \(i\).
• Độ phức tạp sàng đếm ước là:

Với \(M \le 10^7\) là chấp nhận được trong C++ tối ưu.

Hướng giải quyết

Bước 1: Đọc dữ liệu và tìm \(M = \max(a_i)\)

• Đọc \(n, k\), mảng \(a\).
• Tìm \(M\) để giới hạn sàng đúng mức.

Bước 2: Sàng tính số lượng ước cho mọi số \(\le M\)

• Tạo mảng divCnt[0..M] (kiểu uint16_t hoặc int đều được; int an toàn).
• Thực hiện:
  1. Với \(i\) từ \(1\) tới \(M\):
     • Với \(j\) chạy \(i, 2i, 3i, \dots \le M\):
       • divCnt[j]++
• Khi đó divCnt[x] = d(x).

Bước 3: Xác định \(D_{\max}\) và các vị trí tốt

• Duyệt \(i=1..n\):
  • \(D_{\max} = \max(D_{\max}, d(a_i))\).
• Duyệt lại, thu danh sách pos gồm các chỉ số \(i\) có \(d(a_i)=D_{\max}\).

Bước 4: Tìm đoạn con ngắn nhất chứa đủ \(k\) vị trí tốt

• Nếu pos.size() < k thì không thể, in -1.
• Nếu có, đoạn con ngắn nhất chứa ít nhất \(k\) vị trí tốt sẽ luôn có dạng:
  • lấy \(k\) vị trí tốt liên tiếp trong pos: pos[t] ... pos[t+k-1]
  • độ dài đoạn con tương ứng:

• Lấy min trên mọi \(t\).

Các lỗi hay gặp

• Quên kiểm tra pos.size() < k.
• Sàng đến \(10^7\) dùng kiểu dữ liệu quá lớn gây tràn bộ nhớ (tránh vector<long long>).
• I/O chậm: nên dùng ios::sync_with_stdio(false); cin.tie(nullptr);.

Độ phức tạp

• Thời gian:
  • Sàng đếm ước: \(O(M \log M)\) với \(M = \max(a_i) \le 10^7\)
  • Duyệt mảng và tính đáp án: \(O(n)\)
• Bộ nhớ:
  • Mảng divCnt kích thước \(M+1\): \(O(M)\)
  • Mảng \(a\) và pos: \(O(n)\) (có thể tối ưu không lưu toàn bộ a, nhưng thường vẫn đủ)

Code tham khảo

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

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

    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    int M = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] > M) M = a[i];
    }

    // Sàng đếm số ước cho mọi số <= M
    vector<int> divCnt(M + 1, 0);
    for (int i = 1; i <= M; i++) {
        for (int j = i; j <= M; j += i) {
            divCnt[j]++;
        }
    }

    // Tìm Dmax
    int Dmax = 0;
    for (int i = 1; i <= n; i++) {
        Dmax = max(Dmax, divCnt[a[i]]);
    }

    // Lấy các vị trí có số ước lớn nhất
    vector<int> pos;
    pos.reserve(n);
    for (int i = 1; i <= n; i++) {
        if (divCnt[a[i]] == Dmax) pos.push_back(i);
    }

    if ((int)pos.size() < k) {
        cout << -1 << "\n";
        return 0;
    }

    // Tìm đoạn ngắn nhất chứa k vị trí tốt
    int ans = n + 1;
    for (int t = 0; t + k - 1 < (int)pos.size(); t++) {
        int len = pos[t + k - 1] - pos[t] + 1;
        if (len < ans) ans = len;
    }

    cout << ans << "\n";
    return 0;
}