Submission #1213652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213652		avighna	Hack (APIO25_hack)	C++20	100 / 100	81 ms	964 KiB

hack

#include <bits/stdc++.h>

long long collisions(std::vector<long long> x);

int hack() {
  int l = 5e8, r = 1e9;
  while (l < r) {
    int m = std::midpoint(l, r);
    int b = std::sqrt(m - l + 1);
    std::vector<long long> q;
    for (int i = 1; i <= b; ++i) {
      q.push_back(i);
    }
    for (int i = l + b; i <= m; i += b) {
      q.push_back(i);
    }
    if (m + 1 > b) {
      q.push_back(m + 1);
    }
    if (collisions(q)) {
      r = m;
    } else {
      l = m + 1;
    }
  }
  std::vector<int> div = {l};
  for (int i = 2; i * i <= l; ++i) {
    if (l % i == 0) {
      div.push_back(i);
      if (i * i != l) {
        div.push_back(l / i);
      }
    }
  }
  std::sort(div.begin(), div.end());
  std::vector<int> primes;
  for (int i = 0; i < div.size(); ++i) {
    bool prime = true;
    for (auto &p : primes) {
      if (div[i] % p == 0) {
        prime = false;
      }
    }
    if (prime) {
      primes.push_back(div[i]);
    }
  }
  int prev_l = -1;
  while (l != prev_l) {
    prev_l = l;
    for (auto &p : primes) {
      if ((l / p) * p == l and collisions({1, l / p + 1})) {
        l /= p;
        break;
      }
    }
  }
  return l;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 75 / 75