fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include<stdio.h>
  3. typedef unsigned long u32;
  4. typedef unsigned long long u64;
  5.  
  6. u64 bst(u32 s, u32 e, u64 target)
  7. {
  8. 	u64 m;
  9. 	u64 upper;
  10. 	u64 lower;
  11.  
  12. 	//	printf("%u %u\n", s, e);
  13.  
  14. 	//if (target == 0) {
  15. 	//	return 0;
  16. 	//}
  17.  
  18. 	if (s > e) {
  19. 		return 0;
  20. 	}
  21.  
  22. 	m = ((u64)s + (u64)e) / 2;
  23.  
  24.  
  25. 	lower = (u64)(m - 1) * (u64)(m - 1);
  26. 	upper = (u64)m * (u64)m;
  27.  
  28. 	if (lower> target) {
  29. 		return bst(s, m - 1, target);
  30. 	}
  31. 	else if (upper<target) {
  32. 		return bst(m + 1, e, target);
  33. 	}
  34. 	else if (upper > target && lower == target) {
  35. 		return (m-1);
  36. 	}
  37. 	else {
  38. 		return m;
  39. 	}
  40. }
  41.  
  42. int main()
  43. {
  44. 	u64 l;
  45. 	u64 r;
  46. 	u64 lresult;
  47. 	u64 rresult;
  48. 	u64 temp = ((u64)1024 * (u64)1024 * (u64)1024 * (u64)4) -1;
  49. 	u64 final_result;
  50.  
  51. 	scanf("%lld lld", &l, &r);
  52. 	//l = 1;	r = 16;
  53. 	lresult = bst(0, (u32)temp, l);
  54. 	rresult = bst(0, (u32)temp, r);
  55.  
  56. 	if ((rresult* rresult) > r) {
  57. 		rresult--; // last value
  58. 	}
  59. 	if (lresult == 1) {
  60. 		lresult++;
  61. 	}
  62.  
  63.  
  64. 	final_result = (r - l +1) -(rresult - lresult +1);
  65. 	if (l == 1) {
  66. 		final_result--;
  67. 	}
  68.  
  69. 	printf("%lld\n", final_result);
  70. 	return 0;
  71. }
Success #stdin #stdout 0s 9424KB
comments (?)
stdin
copy 
1 10
stdout
copy 
0
https://ideone.com/wGGoM2
language:
C (gcc 8.3)
created:
4 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!