QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#648577 | #8103. Product | rotcar07 | ML | 7ms | 7732kb | C++23 | 823b | 2024-10-17 19:34:13 | 2024-10-17 19:34:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int lim=3e5;
vector<ll> V;
int k;ll p[105],n;
int main(){
cin>>k>>n;for(int i=1;i<=k;i++) cin>>p[i];
int cur=0;V.push_back(1);
while(++cur<=k){
ll z=p[cur];
for(int i=0;i<V.size()&&V.size()<lim;i++){
if(V[i]*z<=n) V.push_back(V[i]*z);
}
if(V.size()>=lim) break;
}
ll ans=0;
sort(V.begin(),V.end());
auto dfs=[&](auto dfs,int id,ll x) -> void {
if(n/x*x<ans) return;
if(id>=cur){
while(x<=n){
dfs(dfs,id-1,x);
x*=p[id];
}
}
else{
ans=max(ans,x**(upper_bound(V.begin(),V.end(),n/x)-1));
}
};
dfs(dfs,k,1);
cout<<ans<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3652kb
input:
3 30 2 3 7
output:
28
result:
ok 1 number(s): "28"
Test #2:
score: 0
Accepted
time: 7ms
memory: 7732kb
input:
7 939341491978215167 2 3 19 43 47 53 61
output:
939207819748596228
result:
ok 1 number(s): "939207819748596228"
Test #3:
score: -100
Memory Limit Exceeded
input:
16 997257405471326207 2 3 5 11 19 23 37 41 47 53 59 61 73 79 89 97
output:
997257095125632000