QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#364499#8103. Productckiseki#ML 1ms4008kbC++201.8kb2024-03-24 14:51:432024-03-24 14:51:45

Judging History

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

  • [2024-03-24 14:51:45]
  • 评测
  • 测评结果:ML
  • 用时:1ms
  • 内存:4008kb
  • [2024-03-24 14:51:43]
  • 提交

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

  vector<int> has(maxn);
  int k;
  cin >> k;
  int64_t N;
  cin >> N;

  for (int i = 0; i < k; i++) {
    int p;
    cin >> p;
    has[p] = true;
  }

  vector<int64_t> 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] <= N) {
        prod *= prs[i];
        self(self, i + 1, r, prod);
      }
  };
  dfs(dfs, 9, prs.size(), 1);
  auto upp = ns;
  ns.clear();
  dfs(dfs, 0, 9, 1);
  auto low = ns;
  ns.clear();
  
  sort(all(low));
  sort(all(upp));

  orange(all(upp));
  orange(all(low));

  int64_t ans = 1;
  for (int64_t x : low) {
    debug(x);
    auto it = upper_bound(all(upp), N / x);
    if (it != upp.begin())
      ans = max(ans, *prev(it) * x);
  }
  cout << ans << '\n';

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3588kb

input:

3 30
2 3 7

output:

28

result:

ok 1 number(s): "28"

Test #2:

score: 0
Accepted
time: 1ms
memory: 4008kb

input:

7 939341491978215167
2 3 19 43 47 53 61

output:

939207819748596228

result:

ok 1 number(s): "939207819748596228"

Test #3:

score: -100
Memory Limit Exceeded

input:

16 997257405471326207
2 3 5 11 19 23 37 41 47 53 59 61 73 79 89 97

output:

997257095125632000

result: