fork download
copy 
  1.  
  2. //update : làm người bình thường
  3. #pragma GCC optimize("O3,unroll-loops")
  4. #include <bits/stdc++.h>
  5. #ifdef _OPENMP
  6. #include <omp.h>
  7. #endif
  8.  
  9. #if LOCAL
  10. #include <algo/debug.h>
  11. #endif
  12.  
  13. using namespace std;
  14. using ll = long long;
  15.  
  16. const int MOD = 1e9 + 7;
  17. const int LIMIT = 1e6 + 7;
  18. const ll INF = LLONG_MAX;
  19.  
  20. vector<ll> sieve(int lim) {
  21.     vector<bool> isprime(lim + 1, true);
  22.     isprime[0] = isprime[1] = false;
  23.     for (int i = 2; i * i <= lim; ++i) {
  24.         if (isprime[i])
  25.             for (int j = i * i; j <= lim; j += i)
  26.                 isprime[j] = false;
  27.     }
  28.     vector<ll> primes;
  29.     primes.reserve((size_t)(lim / log(lim)));
  30.     for (int i = 2; i <= lim; ++i) {
  31.         if (isprime[i])
  32.             primes.push_back(i);
  33.     }
  34.     return primes;
  35. }
  36.  
  37. vector<ll> get(int m, const vector<ll>& primes) {
  38.     int sz = primes.size();
  39.     int imax = sz;
  40.     for (int i = 0; i < sz - 1; ++i) {
  41.         if (primes[i] * primes[i + 1] > m) {
  42.             imax = i;
  43.             break;
  44.         }
  45.     }
  46.  
  47.     size_t totalcount = 0;
  48.     for (int i = 0; i < imax; ++i) {
  49.         ll limit_i = m / primes[i];
  50.         auto it = upper_bound(primes.begin() + i + 1, primes.end(), limit_i);
  51.         totalcount += (it - (primes.begin() + i + 1));
  52.     }
  53.  
  54.     vector<ll> semi;
  55.     semi.reserve(totalcount);
  56.  
  57.     int numthreads = 1;
  58.     vector<vector<ll>> localres(numthreads);
  59.     for (int i = 0; i < numthreads; i++) {
  60.         localres[i].reserve(totalcount / numthreads + 100);
  61.     }
  62.  
  63.     for (int i = 0; i < imax; ++i) {
  64.         int tid = 0;
  65.  
  66.         ll limit_i = m / primes[i];
  67.         auto startit = primes.begin() + i + 1;
  68.         auto endit = upper_bound(startit, primes.end(), limit_i);
  69.         int cnt = endit - startit;
  70.         if (cnt <= 0) continue;
  71.         vector<ll> temp(cnt);
  72.         #pragma omp simd
  73.         for (int k = 0; k < cnt; k++) {
  74.             temp[k] = primes[i] * (*(startit + k));
  75.         }
  76.         localres[tid].insert(localres[tid].end(), temp.begin(), temp.end());
  77.     }
  78.  
  79.     for (int i = 0; i < numthreads; i++) {
  80.         semi.insert(semi.end(), localres[i].begin(), localres[i].end());
  81.     }
  82.  
  83.     sort(semi.begin(), semi.end());
  84.     return semi;
  85. }
  86.  
  87. inline ll solve(const vector<ll>& semi, int tar) {
  88.     const ll* first = semi.data();
  89.     const ll* last = first + semi.size();
  90.     const ll* res = std::upper_bound(first, last, tar);
  91.     if (res == first) return -1;
  92.     return *(res - 1);
  93. }
  94.  
  95. signed main() {
  96.     cin.tie(nullptr), cout.tie(nullptr)->ios_base::sync_with_stdio(false);
  97.  
  98.     #define task "sol"
  99.     if (fopen(task ".inp", "r")) {
  100.         freopen(task ".inp", "r", stdin), freopen(task ".out", "w", stdout);
  101.     }
  102.  
  103.     int t;
  104.     cin >> t;
  105.     vector<int> query(t);
  106.     int lim = 0;
  107.     for (int i = 0; i < t; ++i) {
  108.         cin >> query[i];
  109.         lim = max(lim, query[i]);
  110.     }
  111.  
  112.     vector<ll> primes = sieve(lim);
  113.     vector<ll> semi = get(lim, primes);
  114.  
  115.     for (int tar : query) {
  116.         cout << solve(semi, tar) << "\n";
  117.     }
  118.  
  119.     return 0;
  120. }
Success #stdin #stdout 0s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3S9SxP
language:
C++14 (clang 8.0)
created:
20 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!