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
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#include <cstdio>
#include <cstdlib>

#include <ctime>
#include <cassert>
#include <cstdint>

#include <algorithm>

typedef unsigned long long int llu;

static const int NUMS_COUNT = 25;

llu nums[NUMS_COUNT] = { 0 };

static const int CACHE_SIZE = 38 * 1024;
llu bin_cache[NUMS_COUNT][CACHE_SIZE] = { 0 };
int bin_cache_entries[NUMS_COUNT];
llu max_for_cache[NUMS_COUNT];

int bin_lookup(int nprime, llu bound) {
	int a = 0;
	int b = bin_cache_entries[nprime];
	while (a + 1 < b) {
		const int mid = (a + b) / 2;
		if (bin_cache[nprime][mid] <= bound) {
			a = mid;
		}
		else {
			b = mid;
		}
	}
	return a + 1;
}

void make_bin_cache(int nprimes, llu bound) {
	{
		const int p = nums[0];
		int cachent = 1;
		llu j = p;
		bin_cache[0][0] = 0;
		while (j <= bound / p) {
			bin_cache[0][cachent] = j;
			cachent++;
			j *= p;
		}
		bin_cache_entries[0] = cachent;
		max_for_cache[0] = j;
	}

	for (int i = 1; i < nprimes; i++) {
		const int p = nums[i];
		int cachent = 0;
		llu j = 0;
		const llu max_prev = max_for_cache[i - 1];
		const int bound_prev = bin_cache_entries[i - 1];

		int mypointer = 0, backpointer = 0;

		while (cachent < CACHE_SIZE && backpointer < bound_prev && j < max_prev && j <= bound / p) {
			if (j < p) {
				// In this case we copy previous table
				bin_cache[i][cachent] = bin_cache[i - 1][cachent];
				backpointer++;
				j = std::min(bin_cache[i - 1][backpointer], (llu)p);
			}
			else {
				// More complicated case
				bin_cache[i][cachent] = j;
				const llu c1 = bin_cache[i - 1][backpointer];
				const llu c2 = bin_cache[i][mypointer + 1] * p;
				if (c1 <= c2) {
					j = c1;
					backpointer++;
				}
				if (c1 >= c2) {
					j = c2;
					mypointer++;
				}
			}
			cachent++;
		}
		bin_cache_entries[i] = cachent;
		max_for_cache[i] = j;
	}
}

llu count(int nprime, llu bound) {
	if (nprime == -1) {
		return 1;
	}

	if (bound < max_for_cache[nprime]) {
		return bin_lookup(nprime, bound);
	}

	const llu p = nums[nprime];

	llu ret = count(nprime - 1, bound);
	if (bound >= p) {
		ret += count(nprime, bound / p);
	}

	return ret;
}

bool checknum(int nprimes, llu num) {
	for (int i = 0; i < nprimes; i++) {
		const llu p = nums[i];
		while (num % p == 0) {
			num /= p;
		}
	}

	return (num == 1);
}

inline llu hustle(int nprimes, int ttl, const llu current, llu N) {
	if (ttl == 0) {
		return current;
	}

	llu best = current;
	for (int i = ttl - 1; i < nprimes; i++) {
		const llu p = nums[i];
		llu c = current;
		while (c <= N / p) {
			best = std::max(best, hustle(i, ttl - 1, c, N));
			c *= p;
		}
	}

	return best;
}

llu find_highest_bounded(int nprimes, llu N) {
	static const llu LINEAR_TRESHOLD = 256 * 1024;

	llu a = 0, b = N + 1;
	const llu looked_up = count(nprimes - 1, N);

	// Try to make lower bound better
	if (N > nums[0]) {
		a = hustle(nprimes, std::min(nprimes, 4), 1, N);
	}

	// Binary search to make search range narrower
	while (b - a > LINEAR_TRESHOLD) {
		const llu mid = (a + b) / 2;
		const llu c = count(nprimes - 1, mid);
		assert(c <= looked_up);
		if (c < looked_up) {
			a = mid;
		}
		else {
			b = mid;
		}
	}

	// Linear lookup
	llu i;
	for (i = b - 1; i > a; i--) {
		if (checknum(nprimes, i)) {
			return i;
		}
	}

	assert(checknum(nprimes, i));
	return i;
}

int main() {
	int k;
	llu N;
	scanf("%d %llu", &k, &N);

	for (int i = 0; i < k; i++) {
		scanf("%llu", nums + i);
	}

	std::sort(nums, nums + k);

	make_bin_cache(k, std::max(100ULL, N + 1));

	const llu response = find_highest_bounded(k, N);
	printf("%lld\n", response);

	return 0;
}