fork(11) download
copy 
  1. typedef unsigned int uint32;
  2. typedef unsigned long long uint64;
  3.  
  4. #define UINT64USE
  5. //#define UINT128USE
  6.  
  7. const uint32 N = 1000; // max number is ~7131 for 64 bit values ( 18 446 744 073 709 551 616 )
  8.  
  9. #include <chrono>
  10. #include <string>
  11. #include <vector>
  12. #include <iostream>
  13. #include <stdlib.h>
  14.  
  15. typedef unsigned long long mainType;
  16.  
  17. typedef std::chrono::high_resolution_clock high_resolution_clock;
  18. typedef std::chrono::milliseconds milliseconds;
  19.  
  20. // Array of powers
  21. mainType powers[N];
  22.  
  23. mainType p5(mainType x)
  24. {
  25. 	return x * x * x * x * x;
  26. }
  27.  
  28. milliseconds duration_cast_ms(high_resolution_clock::time_point minus)
  29. {
  30. 	return std::chrono::duration_cast<milliseconds>(high_resolution_clock::now() - minus);
  31. }
  32.  
  33. void clearLine()
  34. {
  35. 	for (int i = 0; i < 77; ++i)
  36. 	{
  37. 		std::cout << " ";
  38. 	}
  39. 	std::cout << "\r";
  40. }
  41.  
  42. int main()
  43. {
  44. 	high_resolution_clock::time_point _start = high_resolution_clock::now();
  45. 	milliseconds speedTime;
  46. 	std::vector<uint32> foundItems;
  47. 	std::cout << "Building table of powers 1 - " << N << "^5\n";
  48. 	uint32 mpow = 0;
  49.  
  50. 	for (uint32 i = 1; i < N; ++i)
  51. 	{
  52. 		powers[i] = p5(i);
  53. 	}
  54.  
  55. 	speedTime = duration_cast_ms( _start );
  56. 	std::cout << "Table ready. Building time: " << ((double)speedTime.count() / 1000 ) << "s, starting search...\n\n";
  57.  
  58. 	uint64 counter = 1, speed = 0, hitsspeed = 0;
  59. 	uint32 foundVal = 0, nextIndex = 0;
  60. 	mainType sum = 0U, baseSum = 0U;
  61.  
  62. 	uint32 lastRangeIndex = 5;
  63.  
  64. 	uint32 ix0 = 0x01;
  65. 	uint32 ix1 = 0x01;
  66. 	uint32 ix2 = 0x01;
  67. 	uint32 ix3 = 0x01;
  68. 	uint32 fVal;
  69.  
  70. 	for (ix0 = 1; ix0 < N; ++ix0)
  71. 	{
  72. 		for (ix1 = 1; ix1 < ix0; ++ix1)
  73. 		{
  74. 			for (ix2 = 1; ix2 < ix1; ++ix2)
  75. 			{
  76. 				baseSum = powers[ix2] + powers[ix1] + powers[ix0];
  77. 				while (lastRangeIndex > 0 && powers[lastRangeIndex] > baseSum)
  78. 				{
  79. 					--lastRangeIndex;
  80. 				};
  81. 				for (ix3 = 1; ix3 < ix2; ++ix3)
  82. 				{
  83. 					fVal = (ix3 + ix2 + ix1 + ix0 - lastRangeIndex) % 30;
  84. 					if ( fVal )
  85. 					{
  86. 						ix3 += 30 - fVal;
  87. 					}
  88. 					if (ix3 >= ix2)
  89. 					{
  90. 						break;
  91. 					}
  92. 					sum = baseSum + powers[ix3];
  93.  
  94. 					/* 128 only
  95. 					nextIndex = sum.GetL();
  96. 					if (((nextIndex & 0xF) > 0) && ((nextIndex & 0x1) == 0))
  97. 					{
  98. 						// filter odd values
  99. 						continue;
  100. 					}
  101. 					*/
  102.  
  103. 					while (lastRangeIndex < (N - 1) && powers[lastRangeIndex] < sum)
  104. 					{
  105. 						++lastRangeIndex;
  106. 					};
  107. 					if (lastRangeIndex == (N - 1))
  108. 					{
  109. 						break;
  110. 					}
  111. 					foundVal = sum == powers[lastRangeIndex] ? lastRangeIndex : 0;
  112. 					if (foundVal > 0)
  113. 					{
  114. 						// clear line
  115. 						clearLine();
  116. 						for (auto ind : foundItems)
  117. 						{
  118. 							if ((foundVal % ind) == 0)
  119. 							{
  120. 								// duplicate
  121. 								//foundVal = 0;
  122. 								break;
  123. 							}
  124. 						}
  125. 						if (foundVal != 0)
  126. 						{
  127. 							std::cout << "found: ";
  128. 							std::cout << ix0 << "^5 ";
  129. 							std::cout << ix1 << "^5 ";
  130. 							std::cout << ix2 << "^5 ";
  131. 							std::cout << ix3 << "^5 ";
  132. 							speedTime = duration_cast_ms(_start);
  133. 							// it/ms: iterations per millisecond, it: total iterations, spd:
  134. 							std::cout << "it/ms: " << (counter / (uint64)speedTime.count()) << " it: " << counter << "\n";
  135. 						}
  136. 						else
  137. 						{
  138. 							std::cout << "duplicate";
  139. 						}
  140. 					}
  141. 					else
  142. 					{
  143. 						if (( 30 + ix3) >= ix2)
  144. 						{
  145. 							break;
  146. 						}
  147. 					}
  148. 					// displaying some progress
  149. 					counter++;
  150. 					if ((counter & 0xFFFFFFF) == 0)
  151. 					{
  152. 						clearLine();
  153. 						std::cout << ix0 << "^5 ";
  154. 						std::cout << ix1 << "^5 ";
  155. 						std::cout << ix2 << "^5 ";
  156. 						std::cout << ix3 << "^5 ";
  157.  
  158. 						speedTime = duration_cast_ms(_start);
  159. 						// it/ms: iterations per millisecond, it: total iterations, spd:
  160. 						std::cout << "it/ms: " << (counter / (uint64)speedTime.count()) << " it: " << counter << "\r";
  161. 					}
  162. 				}
  163. 			}
  164. 		}
  165. 	}
  166.  
  167. 	clearLine();
  168.  
  169. 	milliseconds time = duration_cast_ms(_start);
  170. 	std::cout << "\nDone in: " << ( double(time.count()) / 1000 ) << "s\n" << "Total iterations: " << counter << "\n";
  171. 	speed = counter / (uint64)time.count();
  172. 	std::cout << "cnt/ms: " << speed << " itr/ms \n";
  173.  
  174.  
  175. 	getchar();
  176. 	return 0;
  177. }
Time limit exceeded #stdin #stdout 5s 3480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SpZgcu
language:
C++14 (gcc 8.3)
created:
7 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!