#include <cstdio> #include <algorithm> using namespace std; typedef long long ll; static int primes[100]; static ll divs[100]; static ll n; static ll best = 0; static ll* smallend; static int smallsize; static ll small[855000]; #define BR 6 static void brute(ll sofar, int i){ if(i==BR){ small[smallsize++] = sofar; return; } while(sofar < divs[i]){ brute(sofar, i+1); sofar *= primes[i]; } brute(sofar, i+1); } template<int i> static void solve(ll sofar){ while(sofar < divs[i]){ solve<i-1>(sofar); sofar *= primes[i]; } solve<i-1>(sofar); } template<> void solve<-1>(ll sofar){ auto it = upper_bound(small, smallend, n / sofar); ll val = sofar * it[-1]; if(val>best) best = val; } int main(){ int k; scanf("%d %lld", &k, &n); for(int i=0; i<k; i++){ int p; scanf("%d", &p); primes[i] = p; } sort(primes, primes + k); int br = 0; if(k < 10){ small[smallsize++] = 1; for(int i=0; i<k; i++){ divs[i] = n/primes[i]+1; } smallend = small + smallsize; } else{ br = BR; swap(primes[br-1], primes[br+1]); for(int i=0; i<k; i++){ divs[i] = n/primes[i]+1; } brute(1, 0); smallend = small + smallsize; sort(small, smallend); } for(int i=0; i<k-br; i++){ primes[i] = primes[br+i]; divs[i] = divs[br+i]; } k -= br; k--; reverse(primes, primes+k); reverse(divs, divs+k); switch(k){ #define K(i) case i: solve<i>(1); break; K(0); K(1); K(2); K(3); K(4); K(5); K(6); K(7); K(8); K(9); K(10); K(11); K(12); K(13); K(14); K(15); K(16); K(17); K(18); K(19); K(20); K(21); K(22); K(23); K(24); K(25); K(26); } printf("%lld\n", best); }
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 109 110 111 112 113 114 | #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; static int primes[100]; static ll divs[100]; static ll n; static ll best = 0; static ll* smallend; static int smallsize; static ll small[855000]; #define BR 6 static void brute(ll sofar, int i){ if(i==BR){ small[smallsize++] = sofar; return; } while(sofar < divs[i]){ brute(sofar, i+1); sofar *= primes[i]; } brute(sofar, i+1); } template<int i> static void solve(ll sofar){ while(sofar < divs[i]){ solve<i-1>(sofar); sofar *= primes[i]; } solve<i-1>(sofar); } template<> void solve<-1>(ll sofar){ auto it = upper_bound(small, smallend, n / sofar); ll val = sofar * it[-1]; if(val>best) best = val; } int main(){ int k; scanf("%d %lld", &k, &n); for(int i=0; i<k; i++){ int p; scanf("%d", &p); primes[i] = p; } sort(primes, primes + k); int br = 0; if(k < 10){ small[smallsize++] = 1; for(int i=0; i<k; i++){ divs[i] = n/primes[i]+1; } smallend = small + smallsize; } else{ br = BR; swap(primes[br-1], primes[br+1]); for(int i=0; i<k; i++){ divs[i] = n/primes[i]+1; } brute(1, 0); smallend = small + smallsize; sort(small, smallend); } for(int i=0; i<k-br; i++){ primes[i] = primes[br+i]; divs[i] = divs[br+i]; } k -= br; k--; reverse(primes, primes+k); reverse(divs, divs+k); switch(k){ #define K(i) case i: solve<i>(1); break; K(0); K(1); K(2); K(3); K(4); K(5); K(6); K(7); K(8); K(9); K(10); K(11); K(12); K(13); K(14); K(15); K(16); K(17); K(18); K(19); K(20); K(21); K(22); K(23); K(24); K(25); K(26); } printf("%lld\n", best); } |