#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 vector<ll> prms; const int N = 5e5; int lst[N + 1]; bool has_two = false; ll solve(ll n, ll i){ if(n <= N){ return lst[n]; } ll res = (has_two) ? 1ll << (63ll - __builtin_clzll(n)) : 1ll; rep(j, i, SZ(prms)){ if(n >= prms[j]){ res = max(res, prms[j] * solve(n / prms[j], j)); } } return res; } int main() { #ifndef LOCAL ios_base::sync_with_stdio(0); cin.tie(0); #endif ll pcnt, n; cin >> pcnt >> n; rep(_, 0, pcnt){ int t1; cin >> t1; if(t1 == 2){ has_two = true; } else { prms.pb(t1); } } rep(i, 1, N + 1){ lst[i] = i; } for(auto& p : prms){ for(int k = 1; k * p <= N; k++){ while(lst[k * p] % p == 0){ lst[k * p] /= p; } } } if(has_two){ rep(i, 1, N + 1){ lst[i] /= (1ll << __builtin_ctz(i)); } } rep(i, 2, N + 1){ if(lst[i] == 1){ lst[i] = i; } else{ lst[i] = lst[i - 1]; } } cout << solve(n, 0) << "\n"; 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 87 88 89 | #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 vector<ll> prms; const int N = 5e5; int lst[N + 1]; bool has_two = false; ll solve(ll n, ll i){ if(n <= N){ return lst[n]; } ll res = (has_two) ? 1ll << (63ll - __builtin_clzll(n)) : 1ll; rep(j, i, SZ(prms)){ if(n >= prms[j]){ res = max(res, prms[j] * solve(n / prms[j], j)); } } return res; } int main() { #ifndef LOCAL ios_base::sync_with_stdio(0); cin.tie(0); #endif ll pcnt, n; cin >> pcnt >> n; rep(_, 0, pcnt){ int t1; cin >> t1; if(t1 == 2){ has_two = true; } else { prms.pb(t1); } } rep(i, 1, N + 1){ lst[i] = i; } for(auto& p : prms){ for(int k = 1; k * p <= N; k++){ while(lst[k * p] % p == 0){ lst[k * p] /= p; } } } if(has_two){ rep(i, 1, N + 1){ lst[i] /= (1ll << __builtin_ctz(i)); } } rep(i, 2, N + 1){ if(lst[i] == 1){ lst[i] = i; } else{ lst[i] = lst[i - 1]; } } cout << solve(n, 0) << "\n"; return 0; } |