QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#364896#8103. Productckiseki#ML 202ms4304kbC++202.4kb2024-03-24 17:11:152024-03-24 17:11:15

Judging History

你现在查看的是最新测评结果

  • [2024-03-24 17:11:15]
  • 评测
  • 测评结果:ML
  • 用时:202ms
  • 内存:4304kb
  • [2024-03-24 17:11:15]
  • 提交

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 = 2e8;
  vector<int> ns;
  ns.reserve(1319807 + 10);

  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());

  std::make_heap(all(ns));
  for (size_t i = ns.size(); i > 0; i--)
    std::pop_heap(ns.begin(), ns.begin() + i);


  // 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: 0ms
memory: 3604kb

input:

3 30
2 3 7

output:

28

result:

ok 1 number(s): "28"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3836kb

input:

7 939341491978215167
2 3 19 43 47 53 61

output:

939207819748596228

result:

ok 1 number(s): "939207819748596228"

Test #3:

score: 0
Accepted
time: 92ms
memory: 3888kb

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: 202ms
memory: 4304kb

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: 7ms
memory: 3596kb

input:

6 969452367537798143
2 3 5 7 11 13

output:

969402569554298880

result:

ok 1 number(s): "969402569554298880"

Test #6:

score: -100
Memory Limit Exceeded

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: