#include<bits/stdc++.h> #define rep(i,k,n) for(ll i= (ll) k;i< (ll) n;i++) #define all(v) (v).begin(), (v).end() #define SZ(v) (int)((v).size()) #define pb push_back #define ft first #define sd second typedef long long ll; typedef unsigned long long ull; typedef long double ld; const long long INF = 1e18L + 1; const int IINF = 1e9 + 1; using namespace std; template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; } template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) { while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<','; _dbg(sdbg+1, a...); } #ifdef LOCAL #define DBG(...) _dbg(#__VA_ARGS__, __VA_ARGS__) #else #define DBG(...) (__VA_ARGS__) #define cerr if(0)cout #endif ll k, n; vector<ll> p, maxp; ll best_wyn; void rek(ll i, ll mult) { best_wyn = min(best_wyn, n - mult); if (best_wyn < n % mult) { return; } if (i == k) { return; } for (;;) { rek (i + 1, mult); if (mult > maxp[i]) { break; } mult *= p[i]; if (mult > n) { break; } } } int main() { #ifndef LOCAL ios_base::sync_with_stdio(0); cin.tie(0); #endif cin >> k >> n; best_wyn = n; p.resize(k); rep(i, 0, k) { cin >> p[i]; } //random_shuffle(all(p)); sort(all(p)); reverse(all(p)); rep (i, 0, k) { maxp.pb(n / p[i] + 100); } rek(0, 1); cout << n - best_wyn; 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 | #include<bits/stdc++.h> #define rep(i,k,n) for(ll i= (ll) k;i< (ll) n;i++) #define all(v) (v).begin(), (v).end() #define SZ(v) (int)((v).size()) #define pb push_back #define ft first #define sd second typedef long long ll; typedef unsigned long long ull; typedef long double ld; const long long INF = 1e18L + 1; const int IINF = 1e9 + 1; using namespace std; template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; } template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) { while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<','; _dbg(sdbg+1, a...); } #ifdef LOCAL #define DBG(...) _dbg(#__VA_ARGS__, __VA_ARGS__) #else #define DBG(...) (__VA_ARGS__) #define cerr if(0)cout #endif ll k, n; vector<ll> p, maxp; ll best_wyn; void rek(ll i, ll mult) { best_wyn = min(best_wyn, n - mult); if (best_wyn < n % mult) { return; } if (i == k) { return; } for (;;) { rek (i + 1, mult); if (mult > maxp[i]) { break; } mult *= p[i]; if (mult > n) { break; } } } int main() { #ifndef LOCAL ios_base::sync_with_stdio(0); cin.tie(0); #endif cin >> k >> n; best_wyn = n; p.resize(k); rep(i, 0, k) { cin >> p[i]; } //random_shuffle(all(p)); sort(all(p)); reverse(all(p)); rep (i, 0, k) { maxp.pb(n / p[i] + 100); } rek(0, 1); cout << n - best_wyn; return 0; } |