#include <cstdio> #include <cstdlib> #include <vector> #include <algorithm> #include <cmath> using namespace std; #define LIMIT 999900 long long n; inline bool cmp(long long a, long long b){ return a <= n/b; } vector<long long> numbers; inline int findNum(long long x){ return upper_bound(numbers.begin(), numbers.end(), n/x) - numbers.begin(); } vector<long long> primes; long long check(int id, int k, long long soFar){ if(id == k){ return soFar*numbers[findNum(soFar)-1]; } long long ret = check(id+1, k, soFar); while(cmp(soFar, primes[id])){ soFar *= primes[id]; ret = max(check(id+1, k, soFar), ret); } return ret; } int main(){ // numbers.resize(LIMIT); numbers.reserve(LIMIT); int k; scanf("%d%lld", &k, &n); for(int i=0;i<k;++i){ long long p; scanf("%lld", &p); primes.push_back(p); } sort(primes.begin(), primes.end()); // reverse(primes.begin(), primes.end()); numbers.push_back(1); int id = 0; while(id < k && numbers.size() < LIMIT){ long long tmp = 1L; int num = 0; while(cmp(tmp, primes[id])){ tmp*=primes[id]; num += findNum(tmp); } if(numbers.size() + num < LIMIT){ tmp = 1L; int limit = numbers.size(); while(cmp(tmp, primes[id])){ tmp*=primes[id]; for(int i=0;i<limit;++i){ if(cmp(tmp, numbers[i])){ numbers.push_back(tmp*numbers[i]); } else{ break; } } } } else { break; } id++; sort(numbers.begin(), numbers.end()); } if(id == k){ printf("%lld\n", numbers[numbers.size()-1]); return 0; } printf("%lld\n", check(id, k, 1)); 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 | #include <cstdio> #include <cstdlib> #include <vector> #include <algorithm> #include <cmath> using namespace std; #define LIMIT 999900 long long n; inline bool cmp(long long a, long long b){ return a <= n/b; } vector<long long> numbers; inline int findNum(long long x){ return upper_bound(numbers.begin(), numbers.end(), n/x) - numbers.begin(); } vector<long long> primes; long long check(int id, int k, long long soFar){ if(id == k){ return soFar*numbers[findNum(soFar)-1]; } long long ret = check(id+1, k, soFar); while(cmp(soFar, primes[id])){ soFar *= primes[id]; ret = max(check(id+1, k, soFar), ret); } return ret; } int main(){ // numbers.resize(LIMIT); numbers.reserve(LIMIT); int k; scanf("%d%lld", &k, &n); for(int i=0;i<k;++i){ long long p; scanf("%lld", &p); primes.push_back(p); } sort(primes.begin(), primes.end()); // reverse(primes.begin(), primes.end()); numbers.push_back(1); int id = 0; while(id < k && numbers.size() < LIMIT){ long long tmp = 1L; int num = 0; while(cmp(tmp, primes[id])){ tmp*=primes[id]; num += findNum(tmp); } if(numbers.size() + num < LIMIT){ tmp = 1L; int limit = numbers.size(); while(cmp(tmp, primes[id])){ tmp*=primes[id]; for(int i=0;i<limit;++i){ if(cmp(tmp, numbers[i])){ numbers.push_back(tmp*numbers[i]); } else{ break; } } } } else { break; } id++; sort(numbers.begin(), numbers.end()); } if(id == k){ printf("%lld\n", numbers[numbers.size()-1]); return 0; } printf("%lld\n", check(id, k, 1)); return 0; } |