fork download 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cmath>
  4.  
  5. using namespace std;
  6.  
  7. const int n = 5000;
  8. const int m = 5;
  9. const int Dmax = n + 100;
  10. const int nbits = 3 * log2(n);
  11.  
  12. int D, r, itor[Dmax] = {}, rtoi[Dmax];
  13. long long d[n];
  14.  
  15. inline long long cube(int i)
  16. {
  17.     return (long long)i * i * i;
  18. }
  19.  
  20. inline int atob(int a)
  21. {
  22.     int rb;
  23.     if ((rb = itor[a] - r) < 0) rb += D;
  24.     return rtoi[rb];
  25. }
  26.  
  27. inline void PrintSolution(long long *p)
  28. {
  29.     int a, b;
  30.     bool first = true;
  31.  
  32.     cout << *p << ": ";
  33.     for (a = 2; a <= n; a++) {
  34.         if (b = atob(a), b == 0 || b >= a) continue;
  35.         if (*p != cube(a) - cube(b)) continue;
  36.         cout << (first ? first = false, "(" : ", (") << a << ", " << b << ")";
  37.     }
  38.     cout << endl;
  39. }
  40.  
  41. void FindDuplicates(long long *p, long long *q, int depth)
  42. {
  43.     if (q - p < m) return;
  44.     if (depth < 0) return PrintSolution(p);
  45.  
  46.     long long mask = 1LL << depth;
  47.     long long *P = partition(p, q, [&](long long x) {return !(x & mask);});
  48.  
  49.     FindDuplicates(p, P, depth - 1);
  50.     FindDuplicates(P, q, depth - 1);
  51. }
  52.  
  53. int main(void)
  54. {
  55.     int a, b, i;
  56.  
  57.     for (D = n + 1; D <= Dmax; D++) {
  58.         fill(rtoi, rtoi + D, 0);
  59.         for (i = 1; i <= n; i++) {
  60.             r = cube(i) % D;
  61.             if (rtoi[r]) break; else rtoi[r] = i;
  62.         }
  63.         if (i > n) break;
  64.     }
  65.     if (D > Dmax) return cout << "D not found." << endl, 1;
  66.     for (r = 0; r < D; r++) itor[rtoi[r]] = r;
  67.  
  68.     for (r = 1; r < D; r++) {
  69.         for (i = 0, a = 2; a <= n; a++) {
  70.             if (b = atob(a), b == 0 || b >= a) continue;
  71.             d[i++] = cube(a) - cube(b);
  72.         }
  73.         FindDuplicates(d, d + i, nbits);
  74.     }
  75.     return 0;
  76. }
Success #stdin #stdout 0.56s 5300KB
comments (?)
stdin 
Standard input is empty
stdout 
1412774811: (1134, 357), (1155, 504), (1246, 805), (2115, 2004), (4746, 4725)
https://ideone.com/xQD1W8
language:
C++ (gcc 8.3)
created:
69 days ago
visibility:
secret

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!