Advertisement
Anton_NNNNNNNNNNNN

Untitled

May 26th, 2022
721
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. bool pr[100010];
  2. int resh[100010];
  3.  
  4. void run() {
  5.     int n, x, h;
  6.     cin >> n >> x; h = 2;
  7.     int block = int(sqrt(n)) + 10;
  8.  
  9.     vector <int> v;
  10.     for (int i = 2; i < block; i++) {
  11.         if (!resh[i]) {
  12.             v.push_back(i);
  13.             resh[i] = i;
  14.         }
  15.         for (auto& p : v) {
  16.             if (p * i >= block || p > resh[i])
  17.                 break;
  18.             resh[i * p] = p;
  19.         }
  20.     }
  21.     v.erase(v.begin());
  22.  
  23.     for (int num = 0; num <= n; num += block << 1) {
  24.         int mn = min(block, (n - num + 1) >> 1);
  25.         fill(pr, pr + block, false);
  26.         for (auto& p : v) {
  27.             int f = num - num % p;
  28.             f += p * (f < num);
  29.             f += p * (f % 2 == 0);
  30.             for (int i = (f - num) >> 1; i < mn; i += p)
  31.                 if (num + (i << 1) + 1 > p)
  32.                     pr[i] = true;
  33.         }
  34.         for (int i = 0; i < mn; i++)
  35.             if ((num | i) && !pr[i])
  36.                 h = h * x + num + (i << 1) + 1;
  37.     }
  38.     cout << (n >= 2) * h << endl;
  39. }
Advertisement
RAW Paste Data Copied
Advertisement