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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <algorithm>
#include <cstdio>
#include <functional>
#include <vector>

constexpr bool kEnableLogging = false;
long long global_limit;

// bucket1 contains primes between 2 and 11. bucket2 contains primes between 13
// and 97.
constexpr int kBucket1Lower = 2;
constexpr int kBucket1Upper = 11;
constexpr int kBucket2Lower = 13;
constexpr int kBucket2Upper = 97;
std::vector<int> bucket1, bucket2;

// Smooth numbers for primes from bucket1.
std::vector<long long> extra_smooth;

int number_bucket2_smooth;

// Highest smooth number ever encountered.
long long result;

void Rec(const std::vector<int>& bucket, size_t index, long long result, const std::function<void(long long)>& callback) {
  if (index == bucket.size()) {
    callback(result);
    return;
  }
  while (true) {
    Rec(bucket, index + 1, result, callback);
    if (global_limit / result >= bucket[index]) {
      result *= bucket[index];
    } else {
      break;
    }
  }
}

int main() {
  int num_primes;
  scanf("%d%lld", &num_primes, &global_limit);
  for (int i = 0; i < num_primes; ++i) {
    int p;
    scanf("%d", &p);
    if (p >= kBucket1Lower && p <= kBucket1Upper) {
      bucket1.push_back(p);
    }
    if (p >= kBucket2Lower && p <= kBucket2Upper) {
      bucket2.push_back(p);
    }
  }
  // Generate smooth numbers for bucket1. Guaranteed not to exceed ~300k.
  const auto bucket1_callback = [](long long smooth) { extra_smooth.push_back(smooth); };
  Rec(bucket1, 0, 1, bucket1_callback);
  if (kEnableLogging) {
    printf("Found %d extra smooth numbers.\n", extra_smooth.size());
  }
  std::sort(extra_smooth.begin(), extra_smooth.end());

  const auto bucket2_callback = [](long long smooth) {
    ++number_bucket2_smooth;
    // It is guaranteed that extra_smooth() has at least one element (1).
    int l = 0, u = extra_smooth.size() - 1, r = -1;
    while (l <= u) {
      int m = (l + u) / 2;
      if (global_limit / smooth >= extra_smooth[m]) {
        result = std::max(result, extra_smooth[m] * smooth);
        l = m + 1;
      } else {
        u = m - 1;
      }
    }
  };
  Rec(bucket2, 0, 1, bucket2_callback);
  if (kEnableLogging) {
    printf("Found %lld smooth from bucket2.\n", number_bucket2_smooth);
  }
  printf("%lld\n", result);
  return 0;
}