fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector <int> primes;
  6.  
  7. long long gcd (long long a,long long b) {
  8. 	if (b == 0) return a;
  9. 	return(a % b == 0 ? b : gcd(b,a % b));
  10. }
  11.  
  12. long long find (long long n, int m) {
  13. 	int i,j,c;
  14. 	long long lcm,res;
  15. 	res = 0;
  16. 	for (i = 1; i < (1 << m); i++) {
  17. 		c = 0;
  18. 		lcm = 1;
  19. 		for (j = 0; j < m; j++) {
  20. 			if (((i >> j) & 1) == 1) {
  21. 				c++;
  22. 				lcm = (lcm * primes[j]) / gcd(lcm,primes[j]);
  23. 			}
  24. 		}
  25. 		if (c % 2 == 1) {
  26. 			res = res + n / lcm;
  27. 		} else {
  28. 			res = res - n / lcm;
  29. 		}
  30. 	}
  31. 	return res;
  32. }
  33.  
  34. long long solve (int n,long long l,long long r) {
  35. 	int i,j,flag,m;
  36. 	long long res;
  37. 	primes.clear();
  38. 	for (i = 2; i <= n; i++) {
  39. 		flag = 0;
  40. 		for (j = 0; j < primes.size(); j++) {
  41. 			if (i % primes[j] == 0) {
  42. 				flag = 1;
  43. 				break;
  44. 			}
  45. 		}
  46. 		if (flag == 0) {
  47. 			primes.push_back(i);
  48. 		}
  49. 	}
  50. 	m = primes.size();
  51. 	res = find(r,m) - find(l - 1,m);
  52. 	return res;
  53. }
  54.  
  55. int main()
  56. {
  57. 	int t;
  58. 	scanf("%d",&t);
  59. 	while (t --) {
  60. 		int n;
  61. 		long long l,r,ans;
  62. 		scanf("%d",&n);
  63. 		scanf("%lld%lld",&l,&r);
  64. 		ans = solve(n,l,r);
  65. 		printf("%lld\n",ans);
  66. 	}
  67. 	return 0;
  68. }
  69.  
Time limit exceeded #stdin #stdout 5s 3364KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/raK1Ec
language:
C++ (gcc 8.3)
created:
9 years 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!