tuki2501

bedao_r03_kindness.cpp

Nov 28th, 2021
557
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. const int N = 1000005;
  7.  
  8. int sieve[N], cnt[N], cnt2[10][N];
  9.  
  10. signed main() {
  11.   cin.tie(0)->sync_with_stdio(0);
  12.   for (int i = 2; i < N; i++) {
  13.     sieve[i] = 1;
  14.   }
  15.   for (int i = 2; i < N; i++) {
  16.     if (!sieve[i]) continue;
  17.     for (int j = i; j < N; j += i) {
  18.       if (j != i) sieve[j] = 0;
  19.       cnt[j] += 1;
  20.     }
  21.   }
  22.   for (int i = 2; i < N; i++) {
  23.     cnt2[cnt[i]][i]++;
  24.     for (int j = 1; j <= 7; j++) {
  25.       cnt2[j][i] += cnt2[j][i - 1];
  26.     }
  27.   }
  28.   int q; cin >> q;
  29.   while (q--) {
  30.     int a, b, k;
  31.     cin >> a >> b >> k;
  32.     cout << cnt2[k][b] - cnt2[k][a - 1] << '\n';
  33.   }
  34. }
  35.  
RAW Paste Data