#include <cstdio> #include <algorithm> #include <cmath> const int MAX_K = 35; int k; int p[MAX_K]; const int U = 1561013; int wyp[U], ww; void pref(int c, int i, int limit) { if (c <= limit && c >= limit / p[k-1]) { wyp[ww++] = c; //if (ww % 1000 == 0) printf("%d :: %d\n", ww, c); } for (; i < k && p[i] <= limit / c; i++) { pref(c * p[i], i, limit); } } long long ret; int count; void go(long long c, int i, long long limit, long long whole_limit) { int a = std::min<long long>(whole_limit / c, wyp[ww-1]); if (c >= ret / wyp[ww-1] && a >= wyp[0]) { a = *(std::upper_bound(wyp, wyp+ww, a) - 1); ret = std::max(ret, a * c); count++; } for (; i < k && p[i] <= limit / c; i++) { go(c * p[i], i, limit, whole_limit); } } int main() { long long limit; scanf("%d %lld", &k, &limit); for (int i = 0; i < k ; i++) scanf("%d",&p[i]); std::sort(p, p+k); int pr = std::min(291021013, std::max<int>(std::sqrt(limit), p[k-1])); pref(1, 0, pr); //printf("%d :: %d\n",pr,ww); std::sort(wyp, wyp+ww); ret = 1; while (ret <= limit / p[0]) ret *= p[0]; for (int i = 0; i < k; i++) { go(p[i], i, limit / pr * p[i], limit); //printf("count = %d\n", count); } printf("%lld\n", ret); return 0; }
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 | #include <cstdio> #include <algorithm> #include <cmath> const int MAX_K = 35; int k; int p[MAX_K]; const int U = 1561013; int wyp[U], ww; void pref(int c, int i, int limit) { if (c <= limit && c >= limit / p[k-1]) { wyp[ww++] = c; //if (ww % 1000 == 0) printf("%d :: %d\n", ww, c); } for (; i < k && p[i] <= limit / c; i++) { pref(c * p[i], i, limit); } } long long ret; int count; void go(long long c, int i, long long limit, long long whole_limit) { int a = std::min<long long>(whole_limit / c, wyp[ww-1]); if (c >= ret / wyp[ww-1] && a >= wyp[0]) { a = *(std::upper_bound(wyp, wyp+ww, a) - 1); ret = std::max(ret, a * c); count++; } for (; i < k && p[i] <= limit / c; i++) { go(c * p[i], i, limit, whole_limit); } } int main() { long long limit; scanf("%d %lld", &k, &limit); for (int i = 0; i < k ; i++) scanf("%d",&p[i]); std::sort(p, p+k); int pr = std::min(291021013, std::max<int>(std::sqrt(limit), p[k-1])); pref(1, 0, pr); //printf("%d :: %d\n",pr,ww); std::sort(wyp, wyp+ww); ret = 1; while (ret <= limit / p[0]) ret *= p[0]; for (int i = 0; i < k; i++) { go(p[i], i, limit / pr * p[i], limit); //printf("count = %d\n", count); } printf("%lld\n", ret); return 0; } |