fork(11) download
  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
stdin
Standard input is empty
stdout
Standard output is empty