QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#355369 | #8103. Product | ucup-team004# | ML | 0ms | 3600kb | C++20 | 1.7kb | 2024-03-16 16:32:05 | 2024-03-16 16:32:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i64 = long long;
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define PI pair<ll,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
constexpr int P = 100;
vector<int> pri;
bool isprime[P + 1];
map<ll,PI> M;
int k;
ll n,ans;
void dfs(int p,ll x){
if(p==pri.size()){
auto t=M.upper_bound(-x);
ll tmp=1;
if(t!=M.begin()){
t--;
//cerr<<t->fi<<" "<<t->se.fi<<endl;
tmp=t->se.fi;
}
ans=max(x*tmp,ans);
return;
}
dfs(p+1,x);
if(n/pri[p]>=x)dfs(p,x*pri[p]);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::fill(isprime + 2, isprime + P + 1, true);
std::vector<int> primes;
for (int i = 2; i <= P; i++) {
if (!isprime[i]) {
continue;
}
primes.push_back(i);
for (int j = i * i; j <= P; j += i) {
isprime[j] = false;
}
}
//std::cerr << primes.size() << "\n";
cin>>k>>n;
For(i,1,k){
int t;
cin>>t;
pri.pb(t);
}
sort(pri.begin(),pri.end());
int t=min((int)pri.size(),11);
M[-n]=mp(1,0);
for(auto it=M.begin();it!=M.end();it++){
int dq=it->se.se;
ll x=it->se.fi;
//cerr<<it->fi<<" "<<dq<<" "<<x<<endl;
for(int i=dq;i<t&&n/pri[i]>=x;i++){
ll nx=x*pri[i];
if(!M.count(-n/nx)||M[-n/nx].fi<nx){
M[-n/nx]=mp(nx,i);
}
}
}
dfs(t,1);
cout<<ans<<endl;
// int k;
// i64 N;
// std::cin >> k >> N;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
input:
3 30 2 3 7
output:
28
result:
ok 1 number(s): "28"
Test #2:
score: -100
Memory Limit Exceeded
input:
7 939341491978215167 2 3 19 43 47 53 61
output:
939207819748596228