#include <cstdio> #include <vector> using namespace std; const int MAX_POT = 65; const long long INF = 2 * 1e18; vector<long long> prime; vector<vector<long long> > pot; long long n, result; int k; void read() { scanf("%d%lld", &k, &n); for(int i = 0; i < k; ++i) { long long p; scanf("%lld", &p); prime.push_back(p); } } void prepare() { pot.resize(k); for(int i = 0; i < k; ++i) { pot[i].resize(MAX_POT, 1LL); } for(int i = 0; i < k; ++i) { long long p = prime[i], power = p, limit = INF / p; for(int j = 1; j < MAX_POT; ++j) { pot[i][j] = power; if(power < limit) power *= p; else power = INF; } } } void solve(long long number, int it) { long long limit = INF / number; if(it == k - 1) { int L = 0, P = MAX_POT; while(L + 1 < P) { int mid = (L + P) / 2; long long power = pot[it][mid]; if(power < limit and number * power <= n) L = mid; else P = mid; } result = max(result, number * pot[it][L]); return; } for(int i = 0; i < MAX_POT; ++i) { long long power = pot[it][i]; if(power < limit and power * number <= n) solve(number * power, it + 1); else break; } } int main() { read(); prepare(); solve(1LL, 0); printf("%lld", result); 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 | #include <cstdio> #include <vector> using namespace std; const int MAX_POT = 65; const long long INF = 2 * 1e18; vector<long long> prime; vector<vector<long long> > pot; long long n, result; int k; void read() { scanf("%d%lld", &k, &n); for(int i = 0; i < k; ++i) { long long p; scanf("%lld", &p); prime.push_back(p); } } void prepare() { pot.resize(k); for(int i = 0; i < k; ++i) { pot[i].resize(MAX_POT, 1LL); } for(int i = 0; i < k; ++i) { long long p = prime[i], power = p, limit = INF / p; for(int j = 1; j < MAX_POT; ++j) { pot[i][j] = power; if(power < limit) power *= p; else power = INF; } } } void solve(long long number, int it) { long long limit = INF / number; if(it == k - 1) { int L = 0, P = MAX_POT; while(L + 1 < P) { int mid = (L + P) / 2; long long power = pot[it][mid]; if(power < limit and number * power <= n) L = mid; else P = mid; } result = max(result, number * pot[it][L]); return; } for(int i = 0; i < MAX_POT; ++i) { long long power = pot[it][i]; if(power < limit and power * number <= n) solve(number * power, it + 1); else break; } } int main() { read(); prepare(); solve(1LL, 0); printf("%lld", result); return 0; } |