\(\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.5}}}}}\)

\(\color{#ff0000}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{#ff0000}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{#ff0000}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}\) ở đây

\(\color{#300000}{\text{Hint 1 <Cày trâu>}}\)

• Thử xóa từng bộ \(k\) số và tính ước chung lớn nhất của cả dãy đó

Trong tất cả các kết qủa nhận được, đáp án bài toán chính là kết quả lớn nhất

\(\color{#300000}{\text{Hint 2 <Sàng>}}\)

• Ta sẽ thử xét tất cả các số \(p\), và gọi \(f\) số là bội của nó trong mảng, thì ta cần tìm \(p\) lớn nhất thỏa nó là ước của mọi số còn lại trong mảng sau khi xóa \(k\) phần tử

• Ta sẽ xóa các số không phải là bội của \(p\)

Vì ta có \(gcd(p \times k, z) < p\) với \(p \times k\) là bội nguyên của \(p\) và \(z\) không phải là bội của \(p\)

Nếu vậy thì \(p\) sẽ không được nhận với \(f < n - k\), với \(n - k\) là số phần tử còn lại sau khi xóa \(k\) phần tử

• Ngược lại ta sẽ nhận \(p\) và trong tất cả các số \(p\) thỏa mãn ta lấy \(p\) lớn nhất

\(\color{#c01515}{\text{Approach <Sàng>}}\)

• Với mỗi số \(div\), bạn đếm xem trong dãy có bao nhiêu số là bội của nó, nếu số lượng đó \(f >= n - k\) thì nhận số đó

Trong các số được nhận, kết quả cần tìm là \(res = max(div)\)

• Ta gọi \(a[x]\) là số số có giá trị \(x\) trong mảng, ta sẽ xử lí nhanh hơn thay vì phải duyệt lại trong \(O(n)\)

\(\color{#f03030}{\text{Analysis <Sàng>}}\)

• Đô phức tạp thời gian: \(O(n + alphabet \times \log(alphabet))\)

Phần khởi tạo là \(O(n) + O(alphabet)\)

Phần nhận vào là \(O(n)\) là số phần tử

Phần xử lí là \(O(\frac{alphabet}{alphabet}) + O(\frac{alphabet}{alphabet - 1}) + ... + O(\frac{alphabet}{2} + O(\frac{alphabet}{1}) = O(alphabet \times \log(alphabet))\)
đếm

Tại từng \(div\) thì sẽ chạy vòng lặp \(mul\) là \(O(\frac{alphabet}{div})\) lần

Trong trường hợp xấu nhất sẽ phải chạy \(div = alphabet -> 1\)

• Lưu ý rằng \(alphabet\) ở đây là \(3 \times 10^6\), nếu lớn hơn thì ta phải dùng cách khác

\(\color{#009933}{\text{Preference Accepted Code }}\): Sàng

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n + alphabet \times \log(alphabet))\ \color{#7f5f3f}{\text{time}}\ ||\ O(alphabet)\ \color{#7f5f3f}{\text{memory}}}}\)

const int alphabet = 3e6;
int a[alphabet + 1] = {}; /// mang tan so
int main()
{
    int n, k;
    cin >> n >> k;

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

    for (int div = alphabet; div >= 1; --div)
    {
        ll f = 0;
        for (int mul = div; mul <= alphabet; mul += div)
            f += a[mul];

        if (f >= n - k)
        {
            cout << div;
            return 0;
        }
    }
    return 0;
}