#include <cstdio> #include <algorithm> using namespace std; typedef long long ll; const int T = 1000000; int pr1[] = {2, 3, 5, 7, 11, 13, 17, 89, 97}; int pr2[] = {29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 19, 23}; int p[40], tot; ll n, ret; int d, m, num[101000], premax[T + 10]; void dfs1(int d, int x, int y, int v) { if (x <= T) premax[x] = x; else num[++tot] = x; for (int k = d; k < v; k++) { int ny = y / p[k]; int nx = x; while (ny) { dfs1(k + 1, nx * p[k], ny, v); ny /= p[k]; nx *= p[k]; } } } void dfs2(int d, ll x, ll y, int v) { if (y <= T) ret = max(ret, premax[y] * x); else if (tot > 0) ret = max(ret, (*(upper_bound(num, num + tot, y) - 1)) * x); for (int k = d; k < v; k++) { ll ny = y / p[k]; ll nx = x; while (ny) { dfs2(k + 1, nx * p[k], ny, v); ny /= p[k]; nx *= p[k]; } } } int mark[110], k, k1, k2, x; void init() { scanf("%d%lld", &k, &n); for (int i = 0; i < k; i++) { scanf("%d", &x); mark[x] = 1; } for (int i = 0; i < 9; i++) if (mark[pr1[i]]) p[k1++] = pr1[i]; k2 = k1; for (int i = 0; i < 16; i++) if (mark[pr2[i]]) p[k2++] = pr2[i]; } int main() { init(); m = 1000000000; tot = 0; for (int i = 1; i <= T; i++) premax[i] = 0; dfs1(0, 1, m, k1); for (int i = 1; i <= T; i++) premax[i] = max(premax[i], premax[i - 1]); sort(num, num + tot); dfs2(k1, 1, n, k2); tot = 0; for (int i = 1; i <= T; i++) premax[i] = 0; dfs1(k1, 1, m, k2); for (int i = 1; i <= T; i++) premax[i] = max(premax[i], premax[i - 1]); sort(num, num + tot); dfs2(0, 1, n, k1); printf("%lld\n", ret); }
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 | #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; const int T = 1000000; int pr1[] = {2, 3, 5, 7, 11, 13, 17, 89, 97}; int pr2[] = {29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 19, 23}; int p[40], tot; ll n, ret; int d, m, num[101000], premax[T + 10]; void dfs1(int d, int x, int y, int v) { if (x <= T) premax[x] = x; else num[++tot] = x; for (int k = d; k < v; k++) { int ny = y / p[k]; int nx = x; while (ny) { dfs1(k + 1, nx * p[k], ny, v); ny /= p[k]; nx *= p[k]; } } } void dfs2(int d, ll x, ll y, int v) { if (y <= T) ret = max(ret, premax[y] * x); else if (tot > 0) ret = max(ret, (*(upper_bound(num, num + tot, y) - 1)) * x); for (int k = d; k < v; k++) { ll ny = y / p[k]; ll nx = x; while (ny) { dfs2(k + 1, nx * p[k], ny, v); ny /= p[k]; nx *= p[k]; } } } int mark[110], k, k1, k2, x; void init() { scanf("%d%lld", &k, &n); for (int i = 0; i < k; i++) { scanf("%d", &x); mark[x] = 1; } for (int i = 0; i < 9; i++) if (mark[pr1[i]]) p[k1++] = pr1[i]; k2 = k1; for (int i = 0; i < 16; i++) if (mark[pr2[i]]) p[k2++] = pr2[i]; } int main() { init(); m = 1000000000; tot = 0; for (int i = 1; i <= T; i++) premax[i] = 0; dfs1(0, 1, m, k1); for (int i = 1; i <= T; i++) premax[i] = max(premax[i], premax[i - 1]); sort(num, num + tot); dfs2(k1, 1, n, k2); tot = 0; for (int i = 1; i <= T; i++) premax[i] = 0; dfs1(k1, 1, m, k2); for (int i = 1; i <= T; i++) premax[i] = max(premax[i], premax[i - 1]); sort(num, num + tot); dfs2(0, 1, n, k1); printf("%lld\n", ret); } |