fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4.  
  5. using namespace std;
  6.  
  7. int t, n;
  8.  
  9. int _cubic(int x) {
  10. 	int low = 1, right = 1e3 + 11, res = -1;
  11. 	while(low <= right) {
  12. 		ll mid = (low + right) >> 1;
  13. 		if(mid * mid * mid >= x) {
  14. 			right = mid - 1;
  15. 			res = mid;
  16. 		} else {
  17. 			low = mid + 1;
  18. 		}
  19. 	}
  20. 	return res;
  21. }
  22.  
  23. int _five(int x) {
  24. 	int low = 1, right = 65, res = -1;
  25. 	while(low <= right) {
  26. 		int mid = (low + right) >> 1;
  27. 		if(mid * mid * mid * mid * mid >= x) {
  28. 			right = mid - 1;
  29. 			res = mid;
  30. 		} else {
  31. 			low = mid + 1;
  32. 		}
  33. 	}
  34. 	return res;
  35. }
  36.  
  37. bool _square(int nums) {
  38. 	int sqr = sqrt(nums);
  39. 	return sqr * sqr == nums;
  40. }
  41.  
  42. bool _cubics(int nums) {
  43. 	int x = _cubic(nums);
  44. 	return x * x * x == nums;
  45. }
  46.  
  47. int _fives(int nums) {
  48. 	int x = _five(nums);
  49. 	return x * x * x * x * x == nums;
  50. }
  51.  
  52. void solve() {
  53. 	scanf("%d", &n);
  54.  
  55. 	if(_square(n)) {
  56. 		printf("2\n");
  57. 		return;
  58. 	} else if(_cubics(n)) {
  59. 		printf("3\n");
  60. 		return;
  61. 	} else {
  62. 		for(int i = 1; i * i <= n; ++i) {
  63. 			if(_square(n - i * i)) {
  64. 				printf("4\n");
  65. 				return;
  66. 			}
  67. 		}
  68.  
  69. 		for(int i = 1; i * i * i <= n; ++i) {
  70. 			if(_square(n - i * i * i)) {
  71. 				printf("5\n");
  72. 				return;
  73. 			}	
  74. 		}
  75.  
  76. 		if(_fives(n)) {
  77. 			printf("5\n");
  78. 			return;
  79. 		}
  80.  
  81. 		for(int i = 1; i * i * i <= n; ++i) {
  82. 			if(_cubics(n - i * i * i)) {
  83. 				printf("6\n");
  84. 				return;
  85. 			}
  86. 		}
  87.  
  88. 		for(int i = 1; i * i <= n; ++i) {
  89. 			for(int j = i; j * j <= n - i * i; ++j) {
  90. 				if(_square(n - i * i - j * j)) {
  91. 					printf("6\n");
  92. 					return;
  93. 				}
  94. 			}
  95. 		}
  96.  
  97. 		for(int i = 1; i * i * i <= n; ++i) {
  98. 			for(int j = 1; j * j <= n - i * i * i; ++j) {
  99. 				if(_square(n - i * i * i - j * j)) {
  100. 					printf("7\n");
  101. 					return;
  102. 				}
  103. 			}
  104. 		}
  105.  
  106. 		printf("8\n");
  107. 	}
  108. }
  109.  
  110. int main() {
  111. 	scanf("%d", &t);
  112.  
  113. 	while(t--) solve();
  114. 	return 0;
  115. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
3
27
128
33
stdout
copy 
3
4
5
https://ideone.com/BXTWAp
language:
C++ (gcc 8.3)
created:
17 days 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!