\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\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{red}{\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{orange}{\text{Hướng dẫn}}\)

• Mục tiêu: Gọi các số nguyên được nhận là \(t\), xét 2 trường hợp

Khi \(t \geq x\) thì \(t\) có thể là một trong các đáp án (ứng cử viên loại 1)

Khi \(t \leq x\) thì \(kt\) với (min \(k \in \mathbb{N}\) để \(kt \geq x\)) có thể là một trong các đáp án (ứng cử viên loại 2)

Trong số các ứng cử viên chọn giá trị nhỏ nhất

• Nhận xét:

Khi \(t = 0\) thì chọn 0

Khi \(t \geq x\) thì chọn \(t\).

Khi \(t \leq x\) thì max(\(kt\)) thõa mãn là \(3x - 3\) xảy ra khi \(t = x - 1\)

Kết quả là giá trị nhỏ nhất được chọn

\(\color{goldenrod}{\text{Tiếp cận}}\)

• Cách 1: Trâu

Duyệt các giá trị \(v\) từ \(x\) đến \(3x - 3\)

• Nếu tồn tại vị trí \(i\) để \(v\) là bội của \(a_i\) thì cập nhật kết quả

Nếu kết quả chưa được cập nhật sau quá trình duyệt thì dựa trên nhận xét, kết quả sẽ là giá trị nhỏ nhất trong mảng

Cách này \(O(3xn)\) thời gian và \(O(n)\) bộ nhớ

• Cách 2: Trâu nhánh cận

Đặt kết quả ban đầu là \(res = 3x\).

Lần lượt nhận các phần tử \(t\) là giá trị của mảng dữ liệu

• Nếu \(t \geq x\) thì cập nhật kết quả

• Duyệt \(v\) từ \(x\) đến \(res\). Nếu \(v\) chia hết cho \(t\) thì cập nhật kết quả

Cách này \(O(3xn)\) thời gian và \(O(1)\) bộ nhớ

Lưu ý nếu sàng bằng lưu giá trị vào mảng và dùng mảng đánh dấu thì \(O(3x + n)\) bộ nhớ

• Cách 3: Sàng bội

Đặt kết quả ban đầu là \(res = 3x\).

Lần lượt nhận các phần tử \(t\) là giá trị của mảng dữ liệu

• Nếu \(t \geq x\) thì cập nhật kết quả

• Duyệt các giá trị \(v = kt\) thỏa \(0 \leq v \leq 3x\). Nếu \(v\) chia hết cho \(t\) thì cập nhật kết quả

Cách này \(O(\Sigma(\frac{t}{x}) + n) = O(\frac{max(t) \times n}{x})\) thời gian và \(O(1)\) bộ nhớ

Lưu ý nếu sang bằng lưu giá trị vào mảng và dùng mảng đánh dấu thì \(O(3x + n)\) bộ nhớ

• Cách 4: Sàng bội

Nếu \(x = 0\) thì xuất 0

Đặt kết quả ban đầu là \(res = 3x\). Lập mảng đánh dấu \(a[]\).

Lần lượt nhận các phần tử \(t\) là giá trị của mảng dữ liệu

• Nếu \(t \geq x\) thì cập nhật kết quả

• Nếu \(t < x\) thì đánh dấu \(a[t] = true\)

Duyệt các giá trị \(v\) từ \(1\) đến \(x\)

• Duyệt các bội \(d = kv\) thỏa \(0 \leq d \leq res\)

• • Nếu \(d \geq x\) thì cập nhật kết quả và dừng lặp

Cách này \(O(3x \times log (3x) + n)\) thời gian và \(O(3x)\) bộ nhớ

• Cách 5: Toán học

Với mỗi giá trị \(t\) nhận vào từ mảng dữ liệu, tìm bội gần nhất với nó

Nếu \(t\) chia hết \(x\) thì cập nhật kết quả

Nếu \(t\) không chia hết \(x\). Thì cộng vào phần dư bị thiếu.

• Trừ đi phần \(t\) chia dư cho \(x\)

• Cộng vào giá trị \(x\) vì hiện tại \(t < x\)

Cách này O(n) thời gian và O(1) bộ nhớ

\(\color{green}{\text{Code tham khảo }}\): Cách 1

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(3xn)\ \color{purple}{\text{thời gian}}\ ||\ O(n)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <algorithm>
#include <iostream>

using namespace std;

int main()
{
    int n;
    long long x;
    cin >> n >> x;

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

    for (long long res = x; res <= 3 * x; ++res)
    {
        for (int i = 0; i < n; ++i)
        {
            if (res % a[i] == 0)
            {
                cout << res;
                return 0;
            }
        }
    }

    cout << *min_element(a, a + n);
    return 0;
}

\(\color{green}{\text{Code tham khảo }}\): Cách 2

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(3xn)\ \color{purple}{\text{thời gian}}\ ||\ O(1)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>

using namespace std;

int main()
{
    int n;
    long long x;
    cin >> n >> x;

    long long res = 3 * x;
    for (int i = 0; i < n; ++i)
    {
        long long t;
        cin >> t;

        if (t >= x)
        {
            if (res > t)
                res = t;
        }

        for (long long cur = x; cur < res; ++cur)
        {
            if (cur % t == 0)
            {
                res = cur;
                break;
            }
        }
    }

    cout << res;
    return 0;
}

\(\color{green}{\text{Code tham khảo }}\): Cách 3

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(\Sigma(\frac{t}{x}) + n)\ \color{purple}{\text{thời gian}}\ ||\ O(1)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>

using namespace std;

int main()
{
    int n;
    long long x;
    cin >> n >> x;

    long long res = 3 * x;
    for (int i = 0; i < n; ++i)
    {
        long long t;
        cin >> t;

        if (t >= x)
        {
            if (res > t)
                res = t;
        }

        for (long long cur = 0; cur < res; cur += t)
        {
            if (cur >= x && cur % t == 0)
            {
                res = cur;
                break;
            }
        }
    }

    cout << res;
    return 0;
}

\(\color{green}{\text{Code tham khảo }}\): Cách 4

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(3x \times log(3x) + n)\ \color{purple}{\text{thời gian}}\ ||\ O(3x)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    int n;
    long long x;
    cin >> n >> x;

    if (x == 0)
    {
        cout << 0;
        return 0;
    }

    bool a[3 * x + 3];
    memset(a, false, sizeof(a));

    long long res = 3 * x;
    for (int i = 0; i < n; ++i)
    {
        long long t;
        cin >> t;

        if (t >= x)
        {
            if (res > t)
                res = t;
        }
        else 
        {
            a[t] = true;
        }
    }

    for (long long v = 1; v < x; ++v)
    {
        if (a[v] == true)
        {
            for (long long d = v; d <= 3 * x; d += v)
            {
                a[d] = true;
            }
        }
    }

    for (long long v = x; v <= 3 * x; ++v)
    {
        if (a[v] == true)
        {
            if (res > v)
                res = v;
        }
    }

    cout << res;
    return 0;
}

\(\color{green}{\text{Code tham khảo }}\): Cách 5

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(n)\ \color{purple}{\text{thời gian}}\ ||\ O(1)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>

using namespace std;

int main()
{
    long long n, x;
    cin >> n >> x;

    long long res = 3e18;
    for (int i = 0; i < n; ++i)
    {
        long long t;
        cin >> t;

        long long v = x / t * t;
        if (v < x)
            v += t;

        if (res > v)
            res = v; 
    }

    cout << res;
    return 0;
}