1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include "bits/stdc++.h"
using namespace std;
using Int = long long;

template<class It, class Fun>
void GenerateSmoothNumbers(
        It v_first, It v_last,
        Int a, Int b, Int acc, Fun f) {
    if (acc > b) return;
    if (acc >= a) {
        f(acc);
    }
    for (auto it = v_first; it != v_last; ++it) {
        GenerateSmoothNumbers(it, v_last, a, b, *it * acc, f);
    }
}

Int Sqrt(Int N) {
    Int s = (Int) sqrt((double) N);
    while ((s + 1) * (s + 1) <= N) ++s;
    while (s * s > N) --s;
    assert(s <= 1e9 && s * s <= N && (s + 1) * (s + 1) > N);
    return s;
}

Int FindGreatestSmoothNumber(const vector<int>& ps, Int N) {
    vector<Int> smooth; smooth.reserve(350 * 1000);
    auto it17 = lower_bound(ps.begin(), ps.end(), 17);
    auto it18 = lower_bound(ps.begin(), ps.end(), 18);
    auto push = [&smooth](Int x){smooth.push_back(x);};
    Int sqrtN = Sqrt(N);
    GenerateSmoothNumbers(ps.begin(), it18, sqrtN, 97 * (sqrtN + 1), 1, push);
    GenerateSmoothNumbers(it17, ps.end(), sqrtN, 97 * (sqrtN + 1), 1, push);
    sort(smooth.begin(), smooth.end());

    Int best = 1;
    GenerateSmoothNumbers(ps.begin(), ps.end(), 1, (sqrtN + 1), 1,
        [N, &smooth, &best](Int x){
            auto jt = lower_bound(smooth.begin(), smooth.end(), N / x + 1);
            if (jt != smooth.begin()) {
                best = max(best, x * *prev(jt));
            }
        });
    return best;
}

int main() {
    ios_base::sync_with_stdio(false);
    int k;
    Int N;
    cin >> k >> N;
    vector<int> ps(k);
    for (int i = 0; i < k; ++i) {
        cin >> ps[i];
    }

    sort(ps.begin(), ps.end());

    cout << FindGreatestSmoothNumber(ps, N) << '\n';
}