#include <bits/stdc++.h> using namespace std; #define FOR(i,a,n) for (decltype(n) i = (a), i##__ = (n); i <= i##__; ++i) #define REP(i,n) FOR(i,0,(n)-1) #define FORD(i,a,n) for (decltype(a) i = (a), i##__ = (n); i >= i##__; --i) #define REPD(i,n) FORD(i,(n)-1,0) #define ALL(x) x.begin(), x.end() #define EB emplace_back #define ST first #define ND second #define SZ(x) ((int)x.size()) #define RS resize #define V vector constexpr char nl = '\n'; using LL = long long; using PII = pair<int, int>; using VI = V<int>; using VVI = V<VI>; using VPII = V<PII>; using VVPII = V<VPII>; using VB = V<bool>; using VVB = V<VB>; template<class T, class B> void mini(T &&a, B &&b) { if (b < a) a = b; } template<class T, class B> void maxi(T &&a, B &&b) { if (b > a) a = b; } int pow2(int x) { return x < 2 ? 0 : sizeof(x) * 8 - __builtin_clz(x - 1); } template<class T> struct Off { T a, b; }; template<class T, class X = typename enable_if<!is_same<string, T>::value, T>::type> auto O(T &x) -> Off<decltype(x.begin())> { return {x.begin(), x.end()}; } template<class T> auto O(T &x) -> decltype(cerr << x, x) { return x; } template<class T> auto O(T &x) -> decltype(x.first, x) { return x; } struct Debug { ~Debug() { cerr << nl; } template<class T> auto operator<<(T x) -> decltype(cerr << x, *this) { cerr << O(x); return *this; } template<class T> auto operator<<(T x) -> decltype(x.begin(), typename enable_if<!is_same<string, T>::value, T>::type(), *this) { cerr << "{\n"; for (auto a = x.begin(); a != x.end(); ++a) *this << " " << distance(x.begin(), a) << ": " << O(*a) << '\n'; return *this << "}"; } template<class T, class B> Debug& operator<<(pair<T, B> p) { return *this << "(" << O(p.first) << ", " << O(p.second) << ")"; } template<class T> Debug& operator<<(Off<T> d) { cerr << "{"; for (auto a = d.a, b = d.b; a != b; ++a) *this << O(*a) << (next(a) == b ? "" : ", "); return *this << "}"; } }; struct DebugOff { template<class T> DebugOff& operator<<(T) { return *this; } }; #ifdef DEBUG # define D Debug() #else # define D DebugOff() #endif #define I(x...) #x ": " << x << " " #define TD(X, ...) ostream& operator<<(ostream &os, X &x) { __VA_ARGS__; return os; } //end of templates LL ceil_divide(LL a, LL b) { if(a % b == 0) return a / b; else return a / b + 1; } VI primes; LL n, best = 1; V<LL> cd; void brute(int pos = 0, LL x = 1) { if(pos == SZ(primes)) maxi(best, x); else while(1) { brute(pos + 1, x); if(!(x <= cd[pos] && (x *= primes[pos]) <= n)) break; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int k; cin >> k >> n; primes.RS(k); for(int &p : primes) cin >> p; cd.RS(k); REP(i, k) cd[i] = ceil_divide(n, primes[i]); brute(); cout << 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 | #include <bits/stdc++.h> using namespace std; #define FOR(i,a,n) for (decltype(n) i = (a), i##__ = (n); i <= i##__; ++i) #define REP(i,n) FOR(i,0,(n)-1) #define FORD(i,a,n) for (decltype(a) i = (a), i##__ = (n); i >= i##__; --i) #define REPD(i,n) FORD(i,(n)-1,0) #define ALL(x) x.begin(), x.end() #define EB emplace_back #define ST first #define ND second #define SZ(x) ((int)x.size()) #define RS resize #define V vector constexpr char nl = '\n'; using LL = long long; using PII = pair<int, int>; using VI = V<int>; using VVI = V<VI>; using VPII = V<PII>; using VVPII = V<VPII>; using VB = V<bool>; using VVB = V<VB>; template<class T, class B> void mini(T &&a, B &&b) { if (b < a) a = b; } template<class T, class B> void maxi(T &&a, B &&b) { if (b > a) a = b; } int pow2(int x) { return x < 2 ? 0 : sizeof(x) * 8 - __builtin_clz(x - 1); } template<class T> struct Off { T a, b; }; template<class T, class X = typename enable_if<!is_same<string, T>::value, T>::type> auto O(T &x) -> Off<decltype(x.begin())> { return {x.begin(), x.end()}; } template<class T> auto O(T &x) -> decltype(cerr << x, x) { return x; } template<class T> auto O(T &x) -> decltype(x.first, x) { return x; } struct Debug { ~Debug() { cerr << nl; } template<class T> auto operator<<(T x) -> decltype(cerr << x, *this) { cerr << O(x); return *this; } template<class T> auto operator<<(T x) -> decltype(x.begin(), typename enable_if<!is_same<string, T>::value, T>::type(), *this) { cerr << "{\n"; for (auto a = x.begin(); a != x.end(); ++a) *this << " " << distance(x.begin(), a) << ": " << O(*a) << '\n'; return *this << "}"; } template<class T, class B> Debug& operator<<(pair<T, B> p) { return *this << "(" << O(p.first) << ", " << O(p.second) << ")"; } template<class T> Debug& operator<<(Off<T> d) { cerr << "{"; for (auto a = d.a, b = d.b; a != b; ++a) *this << O(*a) << (next(a) == b ? "" : ", "); return *this << "}"; } }; struct DebugOff { template<class T> DebugOff& operator<<(T) { return *this; } }; #ifdef DEBUG # define D Debug() #else # define D DebugOff() #endif #define I(x...) #x ": " << x << " " #define TD(X, ...) ostream& operator<<(ostream &os, X &x) { __VA_ARGS__; return os; } //end of templates LL ceil_divide(LL a, LL b) { if(a % b == 0) return a / b; else return a / b + 1; } VI primes; LL n, best = 1; V<LL> cd; void brute(int pos = 0, LL x = 1) { if(pos == SZ(primes)) maxi(best, x); else while(1) { brute(pos + 1, x); if(!(x <= cd[pos] && (x *= primes[pos]) <= n)) break; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int k; cin >> k >> n; primes.RS(k); for(int &p : primes) cin >> p; cd.RS(k); REP(i, k) cd[i] = ceil_divide(n, primes[i]); brute(); cout << best; } |