fork download 
  1. // CubeDifferenceQuintuplets9.cpp - 2つの自然数の3乗差が等しくなる5つ組 (mod・再帰ビット二分版)
  2.  
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <cmath>
  6.  
  7. using namespace std;
  8.  
  9. const int n = 5000;
  10. const int m = 5;
  11. const int Dmax = n + 100;
  12. const int nbits = 3 * log2(n);
  13.  
  14. int D, itor[Dmax] = {}, rtoi[Dmax];
  15. int A[n], B[n], P[n];
  16. long long d[n];
  17.  
  18. inline void PrintSolution(int *p, int*q)
  19. {
  20.     cout << d[*p] << ": ";
  21.     sort(p, q, [](int x, int y) {return A[x] < A[y];});
  22.     for_each(p, q, [&](int &x) {
  23.         cout << (&x > p ? ", (" : "(") << A[x] << ", " << B[x] << ")";
  24.     });
  25.     cout << endl;
  26. }
  27.  
  28. void FindDuplicates(int *p, int *q, int depth)
  29. {
  30.     if (q - p < m) return;
  31.     if (depth < 0) return PrintSolution(p, q);
  32.  
  33.     int *P = p, *Q = q;
  34.     long long mask = 1LL << depth;
  35.  
  36.     for (q = p; q < Q; q++) if (!(d[*q] & mask)) p != q ? swap(*p++, *q) : (void)p++;
  37.  
  38.     FindDuplicates(P, p, depth - 1);
  39.     FindDuplicates(p, Q, depth - 1);
  40. }
  41.  
  42. int main(void)
  43. {
  44.     int a, b, i, r, ra, rb;
  45.  
  46.     for (D = n + 1; D <= Dmax; D++) {
  47.         fill(rtoi, rtoi + D, 0);
  48.         for (i = 1; i <= n; i++) {
  49.             r = (long long)i * i * i % D;
  50.             if (rtoi[r]) break; else rtoi[r] = i;
  51.         }
  52.         if (i > n) break;
  53.     }
  54.     if (D > Dmax) return cout << "D not found." << endl, 1;
  55.     for (r = 0; r < D; r++) itor[rtoi[r]] = r;
  56.  
  57.     for (r = 1; r < D; r++) {
  58.         for (i = 0, a = 2; a <= n; a++) {
  59.             ra = itor[a];
  60.             if ((rb = ra - r) < 0) rb += D;
  61.             if (b = rtoi[rb], b == 0 || b >= a) continue;
  62.             A[i] = a;
  63.             B[i] = b;
  64.             d[i] = (long long)a * a * a - (long long)b * b * b;
  65.             P[i] = i;
  66.             i++;
  67.         }
  68.         FindDuplicates(P, P + i, nbits);
  69.     }
  70.     return 0;
  71. }
Success #stdin #stdout 0.72s 5292KB
comments (?)
stdin 
Standard input is empty
stdout 
1412774811: (1134, 357), (1155, 504), (1246, 805), (2115, 2004), (4746, 4725)
https://ideone.com/6RzW0n
language:
C++ (gcc 8.3)
created:
72 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!