Advertisement
Alex_tz307

Numere

Dec 12th, 2020
162
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.20 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. ifstream fin("numere.in");
  6. ofstream fout("numere.out");
  7.  
  8. bool isPrime(int a) {
  9.     if(a == 3)
  10.         return true;
  11.     if(a % 3 == 0)
  12.         return false;
  13.     int rad = sqrt(a);
  14.     for(int i = 5; i <= rad; i += 6)
  15.         if(a % i == 0 || a % (i + 2) == 0)
  16.             return false;
  17.     return true;
  18. }
  19.  
  20. int main() {
  21.     fin.sync_with_stdio(false);
  22.     fout.sync_with_stdio(false);
  23.     fin.tie(nullptr);
  24.     fout.tie(nullptr);
  25.     int task, N;
  26.     fin >> task >> N;
  27.     vector<int> primes;
  28.     primes.emplace_back(2);
  29.     for(int i = 3; i < 333; i += 2)
  30.         if(isPrime(i))
  31.             primes.emplace_back(i);
  32.     vector<int> vals(N + 1);
  33.     int mx = 0, val = 0, sz = primes.size();
  34.     for(int i = 1; i <= N; ++i) {
  35.         int P = 1, x = i, d = 0;
  36.         while(x > 1 && d < sz) {
  37.             int e = 0;
  38.             while(x % primes[d] == 0) {
  39.                 x /= primes[d];
  40.                 ++e;
  41.             }
  42.             P *= (e + 1);
  43.             ++d;
  44.         }
  45.         if(x > 1)
  46.             P *= 2;
  47.         vals[i] = P - 2;
  48.         if(i == 1)
  49.             vals[1] = 0;
  50.         if(vals[i] > mx) {
  51.             mx = vals[i];
  52.             val = i;
  53.         }
  54.     }
  55.     if(task == 1) {
  56.         fout << val;
  57.         return 0;
  58.     }
  59.     int M, T;
  60.     fin >> M >> T;
  61.     vector<int> sum(N + 1);
  62.     for(int i = 1; i <= N; ++i)
  63.         sum[i] = sum[i - 1] + (vals[i] == T);
  64.     long long ans = 0;
  65.     for(int i = 1; i <= N; ++i) {
  66.         int st = i + 1, dr = N, p1 = i;
  67.         while(st <= dr) {
  68.             int mid = (st + dr) >> 1;
  69.             if(sum[mid] - sum[i - 1] >= M) {
  70.                 p1 = mid;
  71.                 dr = mid - 1;
  72.             }
  73.             else
  74.                 st = mid + 1;
  75.         }
  76.         st = i + 1, dr = N;
  77.         int p2 = i;
  78.         while(st <= dr) {
  79.             int mid = (st + dr) >> 1;
  80.             if(sum[mid] - sum[i - 1] <= M) {
  81.                 p2 = mid;
  82.                 st = mid + 1;
  83.             }
  84.             else
  85.                 dr = mid - 1;
  86.         }
  87.         if(sum[p1] - sum[i - 1] == M && sum[p2] - sum[i - 1] == M)
  88.             ans += p2 - p1 + 1;
  89.     }
  90.     fout << ans;
  91. }
  92.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement