QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#364868 | #8103. Product | ckiseki# | ML | 1099ms | 7832kb | C++20 | 2.2kb | 2024-03-24 17:02:20 | 2024-03-24 17:02:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
#include <experimental/iterator>
void orange_(auto s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
using namespace experimental;
copy(L, R, make_ostream_joiner(cerr, ", "));
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
const int maxn = 100;
vector<int> sieve(maxn), prs;
for (int i = 2; i < maxn; i++)
if (!sieve[i])
for (int j = i * 2; j < maxn; j += i)
sieve[j] = true;
for (int i = 2; i < maxn; i++)
if (!sieve[i])
prs.push_back(i);
int k;
int64_t N;
vector<int> has(maxn);
// for (int p : prs)
// has[p] = true;
cin >> k;
cin >> N;
for (int i = 0; i < k; i++) {
int p;
cin >> p;
has[p] = true;
}
orange(all(prs));
const int C = 1e8;
vector<int> ns;
auto dfs = [&](auto self, size_t i, size_t r, int64_t prod) {
if (i >= r) {
ns.push_back(prod);
return;
}
self(self, i + 1, r, prod);
if (has[prs[i]])
while ((__int128)prod * prs[i] <= C) {
prod *= prs[i];
self(self, i + 1, r, prod);
}
};
dfs(dfs, 0, prs.size(), 1);
debug(ns.size());
sort(all(ns));
const int64_t C2 = 3e10;
int cnt = 0;
int64_t ans = 1;
auto dfs2 = [&](auto self, size_t i, size_t r, int64_t prod) {
auto it = upper_bound(all(ns), N / prod);
if (it != ns.begin()) {
ans = max(ans, *prev(it) * prod);
}
if (i >= r) {
return;
}
// ++cnt;
// if (cnt % 10000 == 0) cerr << cnt << endl;
for (size_t j = i; j < r; j++) {
if (has[prs[j]]) {
auto p = prod;
while ((__int128)p * prs[j] <= C2) {
p *= prs[j];
self(self, j + 1, r, p);
}
}
}
};
dfs2(dfs2, 0, prs.size(), 1);
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3928kb
input:
3 30 2 3 7
output:
28
result:
ok 1 number(s): "28"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3900kb
input:
7 939341491978215167 2 3 19 43 47 53 61
output:
939207819748596228
result:
ok 1 number(s): "939207819748596228"
Test #3:
score: 0
Accepted
time: 62ms
memory: 3808kb
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: 144ms
memory: 4284kb
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: 2ms
memory: 4040kb
input:
6 969452367537798143 2 3 5 7 11 13
output:
969402569554298880
result:
ok 1 number(s): "969402569554298880"
Test #6:
score: 0
Accepted
time: 1098ms
memory: 7604kb
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: 3ms
memory: 3676kb
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: 51ms
memory: 4208kb
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: 3680kb
input:
2 780879715975993128 23 47
output:
592020020271363743
result:
ok 1 number(s): "592020020271363743"
Test #10:
score: 0
Accepted
time: 1099ms
memory: 7832kb
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: 3620kb
input:
1 1000000000000000000 7
output:
558545864083284007
result:
ok 1 number(s): "558545864083284007"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3908kb
input:
7 999993 3 5 19 23 31 79 83
output:
994635
result:
ok 1 number(s): "994635"
Test #13:
score: 0
Accepted
time: 21ms
memory: 4004kb
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: 35ms
memory: 4008kb
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: 7ms
memory: 4044kb
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: 3844kb
input:
1 1 11
output:
1
result:
ok 1 number(s): "1"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
2 1 3 7
output:
1
result:
ok 1 number(s): "1"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
1 25 5
output:
25
result:
ok 1 number(s): "25"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
1 80 3
output:
27
result:
ok 1 number(s): "27"
Test #20:
score: 0
Accepted
time: 17ms
memory: 3976kb
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: 90ms
memory: 3888kb
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: 0ms
memory: 3696kb
input:
7 9999999999993 67 71 73 79 83 89 97
output:
9973374165409
result:
ok 1 number(s): "9973374165409"
Test #23:
score: 0
Accepted
time: 4ms
memory: 3680kb
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: 26ms
memory: 3968kb
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: 307ms
memory: 5244kb
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: 498ms
memory: 5236kb
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: 4ms
memory: 3688kb
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: 6ms
memory: 3788kb
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: 499ms
memory: 5328kb
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: 454ms
memory: 5412kb
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: 460ms
memory: 5228kb
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: 0ms
memory: 3852kb
input:
7 80798284478112 67 71 73 79 83 89 97
output:
74134508438681
result:
ok 1 number(s): "74134508438681"
Test #33:
score: 0
Accepted
time: 7ms
memory: 3752kb
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: 36ms
memory: 3784kb
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: 497ms
memory: 5280kb
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: 0ms
memory: 3572kb
input:
7 812983475175210 67 71 73 79 83 89 97
output:
809465694096799
result:
ok 1 number(s): "809465694096799"
Test #37:
score: 0
Accepted
time: 9ms
memory: 3808kb
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: 274ms
memory: 4236kb
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: -100
Memory Limit Exceeded
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