QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #648587 | #8103. Product | rotcar07 | WA | 39ms | 6036kb | C++23 | 798b | 2024-10-17 19:36:15 | 2024-10-17 19:36:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int lim=3e5;
ll V[lim+5];int tot;
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[tot=1]=1;
while(++cur<=k){
ll z=p[cur];
for(int i=1;i<=tot&&tot<lim;i++){
if(V[i]*z<=n) V[++tot]=(V[i]*z);
}
if(tot>=lim) break;
}
ll ans=0;
sort(V+1,V+tot+1);
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+1,V+tot+1,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: 3640kb
input:
3 30 2 3 7
output:
28
result:
ok 1 number(s): "28"
Test #2:
score: 0
Accepted
time: 6ms
memory: 6036kb
input:
7 939341491978215167 2 3 19 43 47 53 61
output:
939207819748596228
result:
ok 1 number(s): "939207819748596228"
Test #3:
score: 0
Accepted
time: 21ms
memory: 5980kb
input:
16 997257405471326207 2 3 5 11 19 23 37 41 47 53 59 61 73 79 89 97
output:
997257095125632000
result:
ok 1 number(s): "997257095125632000"
Test #4:
score: 0
Accepted
time: 36ms
memory: 5984kb
input:
21 999404092522162547 2 3 13 17 19 23 29 31 37 41 43 47 59 61 67 71 73 79 83 89 97
output:
999404022916180674
result:
ok 1 number(s): "999404022916180674"
Test #5:
score: 0
Accepted
time: 15ms
memory: 6036kb
input:
6 969452367537798143 2 3 5 7 11 13
output:
969402569554298880
result:
ok 1 number(s): "969402569554298880"
Test #6:
score: 0
Accepted
time: 39ms
memory: 6000kb
input:
25 999949383078942015 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
output:
999949379900286375
result:
ok 1 number(s): "999949379900286375"
Test #7:
score: 0
Accepted
time: 22ms
memory: 5992kb
input:
16 889438016964538336 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
output:
889426845003977563
result:
ok 1 number(s): "889426845003977563"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
17 299993 2 3 7 11 17 19 23 31 41 43 47 53 71 73 79 83 97
output:
299943
result:
ok 1 number(s): "299943"
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 3656kb
input:
2 780879715975993128 23 47
output:
743311033571904977
result:
wrong answer 1st numbers differ - expected: '592020020271363743', found: '743311033571904977'