#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define rep(i,n,c) for (int i=0;i using vec = vector; template using vvec = vec>; template using vvvec = vec>; using ll = long long; using pii = pair; using pll = pair; template bool chmin(T &a, T b){ if (a>b){ a = b; return true; } return false; } template bool chmax(T &a, T b){ if (a T sum(vec x){ T res=0; for (auto e:x){ res += e; } return res; } template void printv(vec x){ for (auto e:x){ cout<>= 1; } return res; } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); ll N; cin>>N; map LCM; vec A(N,1); set all_divisors; ll m,p,e,t; for (ll i=0;i>m; vec D = {1}; for (ll x=0;x>p>>e; t = pow(p,e); A[i] *= t; LCM[p]; chmax(LCM[p],t); vec nD; for (auto d:D){ nD.append(d); nD.append(d*t); } D = nD; } for (auto d:D){ all_divisors.insert(d); } } vec P; for (auto [p,pe]:LCM){ P.append(pe); } ll n = P.size(); deque> deq = {{1,-1}}; ll prod = -1; while (!deq.empty()){ auto [v,k] = deq.front(); deq.pop_front(); for (ll i=k+1;i selected_P; for (ll i=0;i> S(k,vec(0)); for (ll i=0;i