QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#364799 | #8103. Product | ckiseki# | WA | 1ms | 3924kb | C++20 | 2.2kb | 2024-03-24 16:42:40 | 2024-03-24 16:42:41 |
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());
const int64_t C2 = 1e11;
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()) {
debug(prod, *prev(it));
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: 3628kb
input:
3 30 2 3 7
output:
28
result:
ok 1 number(s): "28"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3924kb
input:
7 939341491978215167 2 3 19 43 47 53 61
output:
741911775343017984
result:
wrong answer 1st numbers differ - expected: '939207819748596228', found: '741911775343017984'