QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#377534 | #8103. Product | SolitaryDream# | AC ✓ | 630ms | 5372kb | C++17 | 2.6kb | 2024-04-05 14:49:45 | 2024-04-05 14:49:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int LIM = 1e18;
int k,n;
inline int IsPrime(int x) {
if (x <= 1) return 0;
for (int i = 2; i * i <= x; ++i) if (x % i == 0) return 0;
return 1;
}
vector<int> v;
void dfs(int x,int s,int lim,vector<int> &a)
{
if(x==a.size())
{
v.push_back(s);
return;
}
int j=s;
while(1)
{
dfs(x+1,j,lim,a);
if(j>lim/a[x])
break;
j*=a[x];
}
}
int getans(int x,int s,int lim,vector<int> &a)
{
if(x==a.size())
{
return *prev(upper_bound(v.begin(),v.end(),lim/s))*s;
}
int j=s;
int ret=0;
while(1)
{
ret=max(ret,getans(x+1,j,lim,a));
if(j>lim/a[x])
break;
j*=a[x];
}
return ret;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin>>k>>n;
// n=1e18;
// vector<vector<int>> vec;
// for (int i = 2; i <= 23; ++i) if (IsPrime(i)) {
// vector<int> cur;
// for (int j = 1; ; ) {
// cur.push_back(j);
// if (j > LIM / i) break;
// j *= i;
// }
// vec.push_back(cur);
// }
// while (vec.size() > 1) {
// nth_element(vec.begin(), vec.end() - 2, vec.end(), [](const vector<int> &a, const vector<int> &b) { return a.size() > b.size(); });
// vector<int> a; a.swap(vec.back()); vec.pop_back();
// vector<int> b; b.swap(vec.back()); vec.pop_back();
// cout << vec.size() << " Merge " << a.size() << ' ' << b.size() << endl;
// vector<int> c;
// for (auto x : a)
// for (auto y : b) {
// if (x > LIM / y) break;
// c.push_back(x * y);
// }
// // if (vec.size() != 1)
// sort(c.begin(), c.end());
// vec.push_back(c);
// }
// cout << vec[0].size() << endl;
vector<int> p,q;
for(int i=1;i<=k;i++)
{
int x;
cin>>x;
if(x<=23)
p.push_back(x);
else
q.push_back(x);
}
// for(int i=6;i<=100;i++)
// {
// int x=i;
// if(!IsPrime(x))
// continue;
// if(x<=23)
// p.push_back(x);
// else
// q.push_back(x);
// }
int ans=0;
dfs(0,1,1e9,p);
sort(v.begin(),v.end());
ans=max(ans,getans(0,1,n,q));
v.clear();
dfs(0,1,1e9,q);
sort(v.begin(),v.end());
ans=max(ans,getans(0,1,n,p));
cout<<ans<<"\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3872kb
input:
3 30 2 3 7
output:
28
result:
ok 1 number(s): "28"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
7 939341491978215167 2 3 19 43 47 53 61
output:
939207819748596228
result:
ok 1 number(s): "939207819748596228"
Test #3:
score: 0
Accepted
time: 18ms
memory: 3676kb
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: 104ms
memory: 3716kb
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: 9ms
memory: 3744kb
input:
6 969452367537798143 2 3 5 7 11 13
output:
969402569554298880
result:
ok 1 number(s): "969402569554298880"
Test #6:
score: 0
Accepted
time: 628ms
memory: 5196kb
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: 58ms
memory: 3696kb
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: 2ms
memory: 3912kb
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: 0
Accepted
time: 0ms
memory: 3552kb
input:
2 780879715975993128 23 47
output:
592020020271363743
result:
ok 1 number(s): "592020020271363743"
Test #10:
score: 0
Accepted
time: 617ms
memory: 5204kb
input:
25 1000000000000000000 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:
1000000000000000000
result:
ok 1 number(s): "1000000000000000000"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
1 1000000000000000000 7
output:
558545864083284007
result:
ok 1 number(s): "558545864083284007"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
7 999993 3 5 19 23 31 79 83
output:
994635
result:
ok 1 number(s): "994635"
Test #13:
score: 0
Accepted
time: 2ms
memory: 3764kb
input:
15 999993 3 5 7 11 13 17 19 23 29 53 59 67 73 79 89
output:
999845
result:
ok 1 number(s): "999845"
Test #14:
score: 0
Accepted
time: 2ms
memory: 3884kb
input:
20 999993 3 5 7 11 17 23 29 37 41 47 53 59 61 67 71 73 79 83 89 97
output:
999949
result:
ok 1 number(s): "999949"
Test #15:
score: 0
Accepted
time: 2ms
memory: 3920kb
input:
20 10 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
1 1 11
output:
1
result:
ok 1 number(s): "1"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
2 1 3 7
output:
1
result:
ok 1 number(s): "1"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
1 25 5
output:
25
result:
ok 1 number(s): "25"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
1 80 3
output:
27
result:
ok 1 number(s): "27"
Test #20:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
14 9999999999993 3 5 11 17 29 37 41 43 47 53 59 67 71 89
output:
9999988946425
result:
ok 1 number(s): "9999988946425"
Test #21:
score: 0
Accepted
time: 26ms
memory: 5164kb
input:
11 9999999999993 2 3 5 7 11 13 17 19 23 29 31
output:
9999995866575
result:
ok 1 number(s): "9999995866575"
Test #22:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
7 9999999999993 67 71 73 79 83 89 97
output:
9973374165409
result:
ok 1 number(s): "9973374165409"
Test #23:
score: 0
Accepted
time: 5ms
memory: 3728kb
input:
17 9999999999993 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
output:
9999983345279
result:
ok 1 number(s): "9999983345279"
Test #24:
score: 0
Accepted
time: 13ms
memory: 4116kb
input:
8 10000000000007 2 3 5 7 11 13 17 19
output:
10000000000000
result:
ok 1 number(s): "10000000000000"
Test #25:
score: 0
Accepted
time: 17ms
memory: 3724kb
input:
19 9999999999993 2 3 5 11 13 17 19 23 37 41 43 47 53 59 61 71 73 79 97
output:
9999997667946
result:
ok 1 number(s): "9999997667946"
Test #26:
score: 0
Accepted
time: 35ms
memory: 5144kb
input:
18 9999999999993 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61
output:
9999998400000
result:
ok 1 number(s): "9999998400000"
Test #27:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
13 9999999999993 5 19 23 29 31 43 59 61 71 73 79 83 89
output:
9999720278125
result:
ok 1 number(s): "9999720278125"
Test #28:
score: 0
Accepted
time: 5ms
memory: 3764kb
input:
18 9999999999993 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
output:
9999983345279
result:
ok 1 number(s): "9999983345279"
Test #29:
score: 0
Accepted
time: 35ms
memory: 5364kb
input:
18 10000000000007 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61
output:
10000000000000
result:
ok 1 number(s): "10000000000000"
Test #30:
score: 0
Accepted
time: 34ms
memory: 4108kb
input:
19 99979004294399 2 3 5 7 11 13 19 23 29 37 41 43 47 61 71 73 79 83 97
output:
99978964734375
result:
ok 1 number(s): "99978964734375"
Test #31:
score: 0
Accepted
time: 56ms
memory: 5320kb
input:
17 100012983161519 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59
output:
100012947714225
result:
ok 1 number(s): "100012947714225"
Test #32:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
7 80798284478112 67 71 73 79 83 89 97
output:
74134508438681
result:
ok 1 number(s): "74134508438681"
Test #33:
score: 0
Accepted
time: 9ms
memory: 3724kb
input:
19 99168391445350 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
output:
99167116466567
result:
ok 1 number(s): "99167116466567"
Test #34:
score: 0
Accepted
time: 7ms
memory: 3620kb
input:
19 999125202087220 7 11 13 17 19 23 29 37 41 43 47 53 59 61 67 71 73 89 97
output:
999122542031933
result:
ok 1 number(s): "999122542031933"
Test #35:
score: 0
Accepted
time: 86ms
memory: 5204kb
input:
17 999903263508863 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59
output:
999903016450000
result:
ok 1 number(s): "999903016450000"
Test #36:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
7 812983475175210 67 71 73 79 83 89 97
output:
809465694096799
result:
ok 1 number(s): "809465694096799"
Test #37:
score: 0
Accepted
time: 10ms
memory: 3712kb
input:
19 993541792230718 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
output:
993535939479217
result:
ok 1 number(s): "993535939479217"
Test #38:
score: 0
Accepted
time: 25ms
memory: 3720kb
input:
19 9996300831103487 2 3 7 11 17 19 23 29 31 37 41 47 53 61 67 79 83 89 97
output:
9996299037850818
result:
ok 1 number(s): "9996299037850818"
Test #39:
score: 0
Accepted
time: 242ms
memory: 5112kb
input:
25 9999702826132809 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:
9999702714170048
result:
ok 1 number(s): "9999702714170048"
Test #40:
score: 0
Accepted
time: 1ms
memory: 3552kb
input:
7 9835185676953190 17 19 37 43 53 73 83
output:
9803452077884603
result:
ok 1 number(s): "9803452077884603"
Test #41:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
17 499993 3 5 7 17 19 23 29 31 37 41 43 47 61 71 73 83 97
output:
499905
result:
ok 1 number(s): "499905"
Test #42:
score: 0
Accepted
time: 240ms
memory: 5172kb
input:
25 10000000000000000 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:
10000000000000000
result:
ok 1 number(s): "10000000000000000"
Test #43:
score: 0
Accepted
time: 23ms
memory: 3680kb
input:
19 99936024569882500 3 5 7 11 13 19 23 29 37 41 43 47 53 59 67 71 73 79 89
output:
99936003073188975
result:
ok 1 number(s): "99936003073188975"
Test #44:
score: 0
Accepted
time: 205ms
memory: 5196kb
input:
17 99968556160199999 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59
output:
99968548850411472
result:
ok 1 number(s): "99968548850411472"
Test #45:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
7 76628348600474422 67 71 73 79 83 89 97
output:
76425966229529167
result:
ok 1 number(s): "76425966229529167"
Test #46:
score: 0
Accepted
time: 40ms
memory: 3624kb
input:
19 99743038863879892 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
output:
99742786671616757
result:
ok 1 number(s): "99742786671616757"
Test #47:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
17 799993 2 5 11 17 19 23 31 37 41 43 47 53 61 67 71 73 97
output:
799940
result:
ok 1 number(s): "799940"
Test #48:
score: 0
Accepted
time: 212ms
memory: 5192kb
input:
17 100000000000000001 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59
output:
100000000000000000
result:
ok 1 number(s): "100000000000000000"
Test #49:
score: 0
Accepted
time: 472ms
memory: 5320kb
input:
23 899966922221289471 2 3 5 7 11 13 17 19 23 29 31 37 41 47 53 59 61 67 73 79 83 89 97
output:
899966916734624375
result:
ok 1 number(s): "899966916734624375"
Test #50:
score: 0
Accepted
time: 439ms
memory: 5372kb
input:
22 899957726806359374 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79
output:
899957721023521875
result:
ok 1 number(s): "899957721023521875"
Test #51:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
9 697531589899549528 59 61 67 71 73 79 83 89 97
output:
689954619477214319
result:
ok 1 number(s): "689954619477214319"
Test #52:
score: 0
Accepted
time: 102ms
memory: 3660kb
input:
22 899460899653457296 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
output:
899460763184084089
result:
ok 1 number(s): "899460763184084089"
Test #53:
score: 0
Accepted
time: 297ms
memory: 5212kb
input:
17 900000000000000001 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59
output:
900000000000000000
result:
ok 1 number(s): "900000000000000000"
Test #54:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
7 766605103129815624 5 13 17 41 47 71 79
output:
766055421142578125
result:
ok 1 number(s): "766055421142578125"
Test #55:
score: 0
Accepted
time: 13ms
memory: 3892kb
input:
16 898093726157755269 2 5 11 13 23 29 37 43 47 53 59 61 67 73 79 97
output:
898093248819554216
result:
ok 1 number(s): "898093248819554216"
Test #56:
score: 0
Accepted
time: 128ms
memory: 3752kb
input:
21 899991869052508159 2 3 5 7 11 17 19 31 37 41 43 47 53 59 61 67 71 73 79 89 97
output:
899991851804777070
result:
ok 1 number(s): "899991851804777070"
Test #57:
score: 0
Accepted
time: 9ms
memory: 3624kb
input:
6 896214613744195199 2 3 5 7 11 13
output:
896168448000000000
result:
ok 1 number(s): "896168448000000000"
Test #58:
score: 0
Accepted
time: 603ms
memory: 5368kb
input:
25 899994612220703999 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:
899994609451736064
result:
ok 1 number(s): "899994609451736064"
Test #59:
score: 0
Accepted
time: 53ms
memory: 3968kb
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 #60:
score: 0
Accepted
time: 630ms
memory: 5192kb
input:
25 900000000000000000 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:
900000000000000000
result:
ok 1 number(s): "900000000000000000"