fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  6. #define pb(x) push_back(x) 
  7. #define N 100005 
  8. #define MOD 1000000007
  9. typedef vector<int> vi;
  10. typedef vector<vi> vvi;
  11. typedef pair<int, int> pii;
  12. typedef long long ll;
  13. typedef unsigned long long ull;
  14.  
  15. #define LSOne(S) (S & (-S))
  16.  
  17. // Cribe
  18. bitset<N> bs; 
  19. vector<int> primes;
  20. void sieve() 
  21. {
  22. 	int n = N;
  23. 	bs.set(); 
  24. 	bs[0] = bs[1] = 0; 
  25. 	for(ll i = 2; i <= n; i++) 
  26. 		if(bs[i])
  27. 		{
  28. 			for(ll j = i * i; j <= n; j += i)
  29. 				bs[j] = 0;
  30. 			primes.push_back(i); 
  31. 		}
  32. }
  33.  
  34. // BIT (Fenwick Tree) methods
  35. vi t; 
  36. void inc(int i, int val)
  37. {
  38. 	for(i++; i <= N; i += LSOne(i))
  39. 		t[i] += val;
  40. }
  41. int rsq(int i)
  42. {
  43. 	int sum = 0;
  44. 	for(i++; i; i -= LSOne(i))
  45. 		sum += t[i];
  46. 	return sum;
  47. }
  48. int rsq(int l, int r)
  49. {
  50. 	return rsq(r) - rsq(l - 1);
  51. }
  52.  
  53. int main() {
  54. 	fastIO;
  55. 	int q, n, k;
  56. 	cin >> q;
  57. 	// Obtain the prime numbers up to 100000
  58. 	sieve();
  59. 	// Initialize the BIT (Fenwick Tree)
  60. 	t = vi(N + 1, 0);
  61. 	for(int i = 0; i < N; i++)
  62. 		inc(i, 1);
  63. 	// Create the array of queries for working with them in offline mode
  64. 	vector<pair<pair<int, int>, int>> queries;
  65. 	for(int i = 0; i < q; i++)
  66. 	{
  67. 		cin >> n >> k;
  68. 		queries.pb(make_pair(make_pair(k, n), i));
  69. 	}
  70. 	// Sort the queries by decreasing K
  71. 	sort(queries.rbegin(), queries.rend());
  72. 	int primeIndex = primes.size() - 1;
  73. 	vector<int> ans(q);
  74. 	for(int i = 0; i < q; i++) 
  75. 	{
  76. 		k = queries[i].first.first;
  77. 		n = queries[i].first.second;
  78. 		// Update (remove) all the elements with prime divisors greater than current query's K
  79. 		while(primeIndex >= 0 && primes[primeIndex] > k)
  80. 		{
  81. 			for(int j = primes[primeIndex]; j < N; j += primes[primeIndex])
  82. 			{
  83. 				if(rsq(j, j) != 0)
  84. 					inc(j, -1);
  85. 			}
  86. 			primeIndex--;
  87. 		}
  88. 		// Set the answer for the query
  89. 		ans[queries[i].second] = rsq(2, n);
  90. 	}
  91. 	for(int i = 0; i < q; i++)
  92. 	{
  93. 		cout << ans[i] << "\n";
  94. 	}
  95. 	return 0;
  96. }
Success #stdin #stdout 0s 15392KB
comments (?)
stdin
copy 
4

10 3

10 4

15 3

5 20
stdout
copy 
6
6
7
4
https://ideone.com/irbeZ3
language:
C++14 (gcc 8.3)
created:
6 years 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!