fork download 
  1. // số i thoả khi mọi ước nguyên tố p của i <= k  
  2. // với mỗi số i thuộc [a, b] thì mình loại bỏ đi hết những ước nguyên tố p <= k
  3. // nếu i là số k-factor thì sau quá trình loại bỏ trên thì i = 1  
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std; 
  7.  
  8. #define fst first
  9. #define snd second 
  10.  
  11. typedef long long ll; 
  12. typedef pair<int, int> ii; 
  13.  
  14. const ll LINF = (ll)1e18; 
  15. const int INF = (int)1e9;
  16.  
  17. const int N = (int)5e6 + 5;  
  18. const int SQRT_B = 44722; 
  19. const int K = (int)1e5 + 5; 
  20.  
  21. int k, a, b; 
  22. int num[N]; 
  23. // [a, b] -> [0, b - a]
  24.  
  25. bool isPrime[K]; 
  26. vector<int> prime; 
  27.  
  28. void sieve() {
  29. 	for (int i = 2; i <= k; i++) isPrime[i] = true;  
  30. 	for (int i = 2; i * i <= k; i++) {
  31. 		if (isPrime[i]) {
  32. 			for (int j = i * i; j <= k; j += i) isPrime[j] = false; 
  33. 		}
  34. 	}
  35. 	for (int i = 2; i <= k; i++) {
  36. 		if (isPrime[i]) prime.push_back(i); 
  37. 	}
  38. }
  39.  
  40. int main() {
  41. 	ios::sync_with_stdio(0); 
  42. 	cin.tie(0); 
  43. 	cin >> k >> a >> b; 
  44.  
  45. 	sieve(); 
  46.  
  47. 	for (int i = a; i <= b; i++) num[i - a] = i;   
  48.  
  49. 	for (int i : prime) { 
  50. 		// for qua những thằng bội của i nằm trong đoạn [a, b]
  51. 		for (int j = (a + i - 1) / i * i; j <= b; j += i) {
  52. 			while (num[j - a] % i == 0) num[j - a] /= i; 
  53. 		}
  54. 	}
  55.  
  56. 	int cnt = 0;   
  57. 	for (int i = a; i <= b; i++) cnt += (num[i - a] == 1); 
  58.  
  59. 	cout << cnt << '\n';
  60. }
  61.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/2Wd6BG
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!