#include <bits/stdc++.h> using namespace std; const int N = 105; int n; long long m; int p[N]; vector<int> possible; long long ans; bool overflows(long long a, long long b) { int l1 = 63 - __builtin_clzll(a) - __builtin_clzll(b) - (-__builtin_clzll(m)); if (l1 > 0) { return true; }else { return (a * b > m); } } void backtrack(const vector<int> &v, int w, long long acc) { possible.push_back(acc); if (w == (int)v.size()) { return; } for (;;) { backtrack(v, w + 1, acc); acc *= v[w]; if (overflows(acc, acc)) { break; } } } void backtrack2(const vector<int> &v, int w, long long acc, const vector<int> &computed) { long long div = m / acc; if (div * div <= m) { int low = 0; int high = computed.size() - 1; int res = -1; while (low <= high) { int mid = (low + high) / 2; if (computed[mid] <= div) { res = mid; low = mid + 1; } else { high = mid - 1; } } ans = max(ans, acc * computed[res]); } if (w < 0) { return; } while (true) { backtrack2(v, w - 1, acc, computed); if (overflows(v[w], acc)) { break; } acc *= v[w]; } } const int p1[] = {5, 71, 19, 79, 41, 83, 67, 47, 29, 17, 2, 13}; int main() { scanf("%d %lld", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &p[i]); } sort(p + 1, p + 1 + n); int size = sizeof(p1) / sizeof(p1[0]); vector<int> v, v2; for (int i = 1; i <= n; i++) { bool git = false; for (int j = 0; j < size; j++) { if (p1[j] == p[i]) { v.push_back(p[i]); git = true; break; } } if (!git) v2.push_back(p[i]); } sort(v.begin(), v.end()); sort(v2.begin(), v2.end()); backtrack(v, 0, 1); vector<int> ans1 = possible; possible.clear(); backtrack(v2, 0, 1); vector<int> ans2 = possible; sort(ans1.begin(), ans1.end()); sort(ans2.begin(), ans2.end()); ans = (long long)max(ans1.back(), ans2.back()) * max(ans1.back(), ans2.back()); backtrack2(v, v.size() - 1, 1, ans2); backtrack2(v2, v2.size() - 1, 1, ans1); printf("%lld\n", ans); 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 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 | #include <bits/stdc++.h> using namespace std; const int N = 105; int n; long long m; int p[N]; vector<int> possible; long long ans; bool overflows(long long a, long long b) { int l1 = 63 - __builtin_clzll(a) - __builtin_clzll(b) - (-__builtin_clzll(m)); if (l1 > 0) { return true; }else { return (a * b > m); } } void backtrack(const vector<int> &v, int w, long long acc) { possible.push_back(acc); if (w == (int)v.size()) { return; } for (;;) { backtrack(v, w + 1, acc); acc *= v[w]; if (overflows(acc, acc)) { break; } } } void backtrack2(const vector<int> &v, int w, long long acc, const vector<int> &computed) { long long div = m / acc; if (div * div <= m) { int low = 0; int high = computed.size() - 1; int res = -1; while (low <= high) { int mid = (low + high) / 2; if (computed[mid] <= div) { res = mid; low = mid + 1; } else { high = mid - 1; } } ans = max(ans, acc * computed[res]); } if (w < 0) { return; } while (true) { backtrack2(v, w - 1, acc, computed); if (overflows(v[w], acc)) { break; } acc *= v[w]; } } const int p1[] = {5, 71, 19, 79, 41, 83, 67, 47, 29, 17, 2, 13}; int main() { scanf("%d %lld", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &p[i]); } sort(p + 1, p + 1 + n); int size = sizeof(p1) / sizeof(p1[0]); vector<int> v, v2; for (int i = 1; i <= n; i++) { bool git = false; for (int j = 0; j < size; j++) { if (p1[j] == p[i]) { v.push_back(p[i]); git = true; break; } } if (!git) v2.push_back(p[i]); } sort(v.begin(), v.end()); sort(v2.begin(), v2.end()); backtrack(v, 0, 1); vector<int> ans1 = possible; possible.clear(); backtrack(v2, 0, 1); vector<int> ans2 = possible; sort(ans1.begin(), ans1.end()); sort(ans2.begin(), ans2.end()); ans = (long long)max(ans1.back(), ans2.back()) * max(ans1.back(), ans2.back()); backtrack2(v, v.size() - 1, 1, ans2); backtrack2(v2, v2.size() - 1, 1, ans1); printf("%lld\n", ans); return 0; } |