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. unordered_set<int> seen;
  9.  
  10. int _cubic(int x) {
  11. 	int low = 1, right = 1e3 + 11, res = -1;
  12. 	while(low <= right) {
  13. 		ll mid = (low + right) >> 1;
  14. 		if(mid * mid * mid >= x) {
  15. 			right = mid - 1;
  16. 			res = mid;
  17. 		} else {
  18. 			low = mid + 1;
  19. 		}
  20. 	}
  21. 	return res;
  22. }
  23.  
  24. bool _square(int nums) {
  25. 	return seen.count(nums);
  26. }
  27.  
  28. bool _cubics(int nums) {
  29. 	int x = _cubic(nums);
  30. 	return x * x * x == nums;
  31. }
  32.  
  33. void solve() {
  34. 	scanf("%d", &n);
  35.  
  36. 	if(_square(n)) {
  37. 		printf("2\n");
  38. 		return;
  39. 	} else if(_cubics(n)) {
  40. 		printf("3\n");
  41. 		return;
  42. 	} else {
  43. 		for(int i = 1; i * i <= n; ++i) {
  44. 			if(_square(n - i * i)) {
  45. 				printf("4\n");
  46. 				return;
  47. 			}
  48. 		}
  49.  
  50. 		for(int i = 1; i * i * i <= n; ++i) {
  51. 			if(_square(n - i * i * i)) {
  52. 				printf("5\n");
  53. 				return;
  54. 			}	
  55. 		}
  56.  
  57. 		for(int i = 1; i * i * i <= n; ++i) {
  58. 			if(_cubics(n - i * i * i)) {
  59. 				printf("6\n");
  60. 				return;
  61. 			}
  62. 		}
  63.  
  64. 		for(int i = 1; i * i <= n; ++i) {
  65. 			for(int j = i; j * j <= n - i * i; ++j) {
  66. 				if(_square(n - i * i - j * j)) {
  67. 					printf("6\n");
  68. 					return;
  69. 				}
  70. 			}
  71. 		}
  72.  
  73. 		for(int i = 1; i * i * i <= n; ++i) {
  74. 			for(int j = 1; j * j <= n - i * i * i; ++j) {
  75. 				if(_square(n - i * i * i - j * j)) {
  76. 					printf("7\n");
  77. 					return;
  78. 				}
  79. 			}
  80. 		}
  81.  
  82. 		printf("8\n");
  83. 	}
  84. }
  85.  
  86. int main() {
  87. 	scanf("%d", &t);
  88.  
  89. 	for(int i = 1; i * i <= 1'000'000'000; ++i)
  90. 		seen.insert(i * i);
  91.  
  92. 	while(t--) solve();
  93. 	return 0;
  94. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
3
27
128
33
stdout
copy 
3
4
5
https://ideone.com/LGzM9w
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!