// PA2017, Iloczyn // Andrzej Pezarski #include <iostream> #include <vector> #include <algorithm> using namespace std; int K; long long N; vector<long long> V; vector<long long> W; long long cnt=0; long long RES=1; void zlicz0() { vector<long long> P(K); for(auto &p:P) cin >> p; for(auto p:P) { while (p<=N) { V.push_back(p); if (p>1000000000) break; p*=p; } } sort(V.begin(), V.end()); } void zlicz1(long long X, long long N0, int i) { if (X<=N0) W.push_back(X); cnt++; for (int j=i; j<V.size(); j++){ if (X>N0/V[j]) break; zlicz1(X*V[j], N0, j+1); } } void zlicz2(long long X, long long N0, int i) { if (X>N0) return; auto it=upper_bound(W.begin(), W.end(), N/X); if (it!=W.begin()) { it--; RES=max(RES, X*(*it)); } for (int j=i; j<V.size(); j++){ if (X>N0/V[j]) break; zlicz2(X*V[j], N0, j+1); } } int main() { cin >> K >> N; zlicz0(); if (N<=1000000000) { W.push_back(1); zlicz2(1, N, 0); } else { zlicz1(1, 10000000, 0); sort(W.begin(), W.end()); zlicz2(1, N/500000, upper_bound(V.begin(), V.end(), 15)-V.begin()); // zlicz2(1, N/1000000, 0); } cout << RES << 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 | // PA2017, Iloczyn // Andrzej Pezarski #include <iostream> #include <vector> #include <algorithm> using namespace std; int K; long long N; vector<long long> V; vector<long long> W; long long cnt=0; long long RES=1; void zlicz0() { vector<long long> P(K); for(auto &p:P) cin >> p; for(auto p:P) { while (p<=N) { V.push_back(p); if (p>1000000000) break; p*=p; } } sort(V.begin(), V.end()); } void zlicz1(long long X, long long N0, int i) { if (X<=N0) W.push_back(X); cnt++; for (int j=i; j<V.size(); j++){ if (X>N0/V[j]) break; zlicz1(X*V[j], N0, j+1); } } void zlicz2(long long X, long long N0, int i) { if (X>N0) return; auto it=upper_bound(W.begin(), W.end(), N/X); if (it!=W.begin()) { it--; RES=max(RES, X*(*it)); } for (int j=i; j<V.size(); j++){ if (X>N0/V[j]) break; zlicz2(X*V[j], N0, j+1); } } int main() { cin >> K >> N; zlicz0(); if (N<=1000000000) { W.push_back(1); zlicz2(1, N, 0); } else { zlicz1(1, 10000000, 0); sort(W.begin(), W.end()); zlicz2(1, N/500000, upper_bound(V.begin(), V.end(), 15)-V.begin()); // zlicz2(1, N/1000000, 0); } cout << RES << endl; return 0; } |