Submission #799383

#	Time	Username	Problem	Language	Result	Execution time	Memory
799383		tch1cherin	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	514 ms	88468 KiB

brunhilda

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e7 + 5;
int fact[MAX_N] = {};
int dp[MAX_N] = {};
bool is_special[MAX_N] = {};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int M, Q;
  cin >> M >> Q;
  vector<int> primes(M);
  for (auto &v : primes) {
    cin >> v;
    is_special[v] = true;
  }
  sort(primes.begin(), primes.end());
  for (int i = 2; i < MAX_N; i++) {
    if (fact[i] == 0) {
      fact[i] = i;
      if (i < MAX_N / i) {
        for (int j = i * i; j < MAX_N; j += i) {
          fact[j] = i;
        }
      }
    }
  }
  int r0 = primes.back(), r1 = primes.back();
  dp[1] = 1;
  for (int i = 2; i < r0; i++) {
    dp[i] = 1;
    int t = i, max_f = -1;
    while (t > 1) {
      max_f = fact[t] > max_f && is_special[fact[t]] ? fact[t] : max_f;
      t /= fact[t];
    }
    r1 = max(r1, i + max_f);
  }
  fill(dp + r0, dp + MAX_N, INT_MAX);
  int val = 1;
  for (int i = r0; i < MAX_N; i++) {
    if (i >= r0) {
      r0 = r1;
      val++;
    }
    if (i >= r0) {
      break;
    }
    dp[i] = val;
    int t = i, max_f = -1;
    while (t > 1) {
      max_f = fact[t] > max_f && is_special[fact[t]] ? fact[t] : max_f;
      t /= fact[t];
    }
    r1 = max(r1, i + max_f);
  }
  while (Q--) {
    int n;
    cin >> n;
    if (dp[n] == INT_MAX) {
      cout << "oo\n";
    } else {
      cout << dp[n] << "\n";
    }
  }
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 60 / 60