#include <iostream> #include <cmath> #define LL unsigned long long #define MAX_LENGTH 110 using namespace std; int get_max_pow(LL n, int prime) { int k = 0; while (n >= prime) { n /= prime; k++; } return k; } LL count(int k, LL N, int *primes, int *selected) { LL result = 1, value; for (int i = 0; i < k; i++) { value = pow(primes[i], selected[i]); if (N / value < result) return N + 1; result *= value; } return result; } int main() { LL N, best = 0, result; int k, value, primes[MAX_LENGTH], pows[MAX_LENGTH], selected[MAX_LENGTH]; bool numbers[MAX_LENGTH]; for (int i = 0; i < MAX_LENGTH; i++) numbers[i] = false; cin >> k >> N; for (int i = 0; i < k; i++) { cin >> value; numbers[value] = true; } k = 0; for (int i = 0; i < MAX_LENGTH; i++) if (numbers[i]) { primes[k] = i; k++; } if (k == 1) { cout << pow(primes[0], get_max_pow(N, primes[0])) << endl; return 0; } for (int i = 0; i < k; i++) { pows[i] = get_max_pow(N, primes[i]); selected[i] = 0; } while (true) { result = count(k, N, primes, selected); if (result == N) { best = N; break; } if (result < N) { if (result > best) best = result; for (int i = k - 1; i >= 0; i--) { if (selected[i] < pows[i] || i==0) { selected[i]++; break; } else { selected[i] = 0; } } } else { int i = k - 1; while (i > 0) { if (selected[i] > 0) { selected[i] = 0; selected[i-1]++; break; } i--; } for (int j = i - 1; j > 0; i--) { if (selected[j] <= pows[j]) { break; } else { selected[j] = 0; selected[j-1]++; } } } if (selected[0] > pows[0]) break; } cout << best << endl; 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 | #include <iostream> #include <cmath> #define LL unsigned long long #define MAX_LENGTH 110 using namespace std; int get_max_pow(LL n, int prime) { int k = 0; while (n >= prime) { n /= prime; k++; } return k; } LL count(int k, LL N, int *primes, int *selected) { LL result = 1, value; for (int i = 0; i < k; i++) { value = pow(primes[i], selected[i]); if (N / value < result) return N + 1; result *= value; } return result; } int main() { LL N, best = 0, result; int k, value, primes[MAX_LENGTH], pows[MAX_LENGTH], selected[MAX_LENGTH]; bool numbers[MAX_LENGTH]; for (int i = 0; i < MAX_LENGTH; i++) numbers[i] = false; cin >> k >> N; for (int i = 0; i < k; i++) { cin >> value; numbers[value] = true; } k = 0; for (int i = 0; i < MAX_LENGTH; i++) if (numbers[i]) { primes[k] = i; k++; } if (k == 1) { cout << pow(primes[0], get_max_pow(N, primes[0])) << endl; return 0; } for (int i = 0; i < k; i++) { pows[i] = get_max_pow(N, primes[i]); selected[i] = 0; } while (true) { result = count(k, N, primes, selected); if (result == N) { best = N; break; } if (result < N) { if (result > best) best = result; for (int i = k - 1; i >= 0; i--) { if (selected[i] < pows[i] || i==0) { selected[i]++; break; } else { selected[i] = 0; } } } else { int i = k - 1; while (i > 0) { if (selected[i] > 0) { selected[i] = 0; selected[i-1]++; break; } i--; } for (int j = i - 1; j > 0; i--) { if (selected[j] <= pows[j]) { break; } else { selected[j] = 0; selected[j-1]++; } } } if (selected[0] > pows[0]) break; } cout << best << endl; return 0; } |