fork download
copy 
  1. /* #define DEBUG */ 
  2. /* #define DEBUG_VOMIT */
  3.  
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <time.h>
  7. #include <stdint.h>
  8.  
  9. #define N_MAX 2500000
  10. #define X_LIMIT  10000000000UL /*10000000UL*/
  11. #define DATA_MAX  4294967295UL 	/* heap_n の初期値 > X_LIMIT */
  12. #define EQUAL 10 /* > 5 */ /* 求める組み合わせの数 */
  13.  
  14. typedef uint64_t DATA;
  15. typedef uint64_t PARA;
  16.  
  17. /* f(n, k) = (n + k)^3 - n^3 とするとき、
  18.  *    f(n + 1, 1) = f(n, 1) + 6 * (n + 1) ... 3 乗差(a) の生成
  19.  *    f(n, k + 1) = f(n, k) + f(n + k, 1) ... 3 乗差(b) の生成
  20.  */
  21.  
  22. static DATA d1[N_MAX];	/* 3 乗差(a): d1[n] = f(n, 1) */
  23. static DATA d[N_MAX];	/* 3 乗差(b): d[n] = f(n, p[n]) */
  24. static PARA p[N_MAX];
  25.  
  26. struct {
  27. 	DATA n;
  28. 	PARA a;
  29. 	PARA b;
  30. } output_stack[EQUAL];
  31.  
  32. static int f_verbose = 0;		/* verbose mode */
  33.  
  34. /* proto-type */
  35. void init_heap(void);
  36. void put_heap(DATA n, PARA a, PARA b);
  37. void get_heap(DATA *n, PARA *a, PARA *b);
  38. void vomit_heap(void);
  39. void findX(int);
  40.  
  41. /* DATA top_heap(void); */
  42. static DATA heap_n[N_MAX];
  43. #define top_heap() heap_n[1]
  44.  
  45. int main(int argc, char **argv)
  46. {
  47.   time_t start, stop;
  48.  
  49.   time(&start);
  50.   if (argc == 2 && *argv[1] == '-' && *(argv[1] + 1) == 'v')
  51.     f_verbose = 1;
  52.  
  53.   findX(4);
  54.   findX(5);  
  55.  
  56.   time(&stop);
  57.   fprintf(stderr, "(time: %ld sec.)\n", stop - start);
  58.   return 0;
  59. }
  60.  
  61. void findX(int iEQUAL) {
  62.   PARA max, i, a, b; /* 配列パラメータ系 */
  63.   DATA diff, new, res, n; /* 3 乗差系 */
  64.   int sp, j;
  65.  
  66.   /* 初期化 */
  67.   d[1] = d1[1] = 7;
  68.   max = p[1] = 1;
  69.   diff = 6;
  70.   for (i = 2; i < N_MAX; i++) {
  71.     d[i] = 0;
  72.     p[i] = 0;
  73.   }
  74.  
  75.   /* heap 初期化 */
  76.   init_heap();
  77.   put_heap(d[1], 1, 1);
  78.  
  79.   for (;;) {
  80.     /* 新たに 3 乗差(a) を生成 -> new */
  81.     diff += 6L;
  82.     new = d1[max] + diff;
  83.     max++;
  84.     d1[max] = new;
  85.     d[max] = new;
  86.     p[max] = 1;
  87.  
  88.     /* 終了条件 1 */
  89.     if (new > X_LIMIT) {
  90.       fprintf(stderr, "3 乗差が範囲(～%ld)を超えた.\n", X_LIMIT);
  91.       vomit_heap();
  92.       exit(0);
  93.     }
  94.     /* 終了条件 2 */
  95.     if (max > N_MAX) {
  96.       fprintf(stderr, "配列パラメータが範囲を超えた(max).n");
  97.       vomit_heap();
  98.       exit(0);
  99.     }
  100.     /* new を heap に積み上げる */
  101.     put_heap(new, 1, max);
  102.  
  103.     /* heap から new 以下の 3 乗差 (組み合わせ確定) を取り出す */
  104.     while((res = top_heap()) < new) {
  105.       sp = 0;
  106.       while (res == top_heap()) {
  107.         get_heap(&n, &a, &b);
  108.         output_stack[sp].n = n;
  109.         output_stack[sp].a = a;
  110.         output_stack[sp].b = b;
  111.         sp++;
  112.       }
  113.       if (f_verbose) { /* verbose mode */
  114.         if (sp >= 2) {
  115.           printf("%ld (%d): ", n, sp);
  116.           for (j = 0; j < sp; j++)
  117.             printf("(%u,%u)  ",
  118.                    output_stack[j].a + output_stack[j].b,
  119.                    output_stack[j].b);
  120.           putchar('\n');
  121.         }
  122.       }
  123.       /* 終了条件 3: 解発見 */
  124.       if (sp == iEQUAL)
  125.         goto label_soluted;
  126.     }
  127.     /* 3 乗差(b) を生成 */
  128.     for (i = 1; i < max; i++) {
  129.       if (new > d[i]) {
  130.         d[i] = d[i] + d1[i + p[i]];
  131.         p[i]++;
  132.         put_heap(d[i], i, p[i]);
  133.       }
  134.     }
  135.   }
  136.  
  137. label_soluted:
  138.   printf("solution :\n");
  139.   printf("%ld\n", output_stack[0].n);
  140.   for (i = 0; i < iEQUAL; i++) {
  141.     PARA a1, a2;
  142.     a1 = output_stack[i].a + output_stack[i].b;
  143.     a2 = output_stack[i].a;
  144.     printf("= %u^3 - %u^3\n", a1, a2);
  145.   }
  146. }
  147.  
  148. /* =========================================== */
  149. /* static DATA heap_n[N_MAX]; */
  150. static PARA heap_a[N_MAX];
  151. static PARA heap_b[N_MAX];
  152.  
  153. void init_heap(void) {
  154.   PARA i;
  155.  
  156.   for (i = 0; i < N_MAX; i++)
  157.     heap_n[i] = DATA_MAX;
  158.   return;
  159. }
  160.  
  161. void put_heap(DATA n, PARA a, PARA b) {
  162.   PARA child, parent, tmp_p;
  163.   DATA tmp_d;
  164.  
  165. #ifdef DEBUG
  166.   fprintf(stderr, "<put_heap>");
  167.   fprintf(stderr, "	%ld, %u, %u\n", n, a, b);
  168. #endif
  169.   child = 1;
  170.   while (heap_n[child] < DATA_MAX)
  171.     child++;
  172.   heap_n[child] = n;
  173.   heap_a[child] = a;
  174.   heap_b[child] = b;
  175.   while (parent = child >> 1,
  176.          (parent >= 1 && heap_n[child] < heap_n[parent])) {
  177.     tmp_d = heap_n[child];			/* swap heap_n */
  178.     heap_n[child] = heap_n[parent];
  179.     heap_n[parent] = tmp_d;
  180.     tmp_p = heap_a[child];			/* swap heap_a */
  181.     heap_a[child] = heap_a[parent];
  182.     heap_a[parent] = tmp_p;
  183.     tmp_p = heap_b[child];			/* swap heap_b */
  184.     heap_b[child] = heap_b[parent];
  185.     heap_b[parent] = tmp_p;
  186. #ifdef DEBUG
  187.     fprintf(stderr, "<put_heap> exchange(%u, %u)\n", child, parent);
  188. #endif
  189.   }
  190. #ifdef DEBUG_VOMIT
  191.   vomit_heap();
  192. #endif
  193.   return;
  194. }
  195.  
  196. void get_heap(DATA *n, PARA *a, PARA *b) {
  197.   PARA child, parent;
  198.  
  199. #ifdef DEBUG
  200.   fprintf(stderr, "<get_heap>");
  201. #endif
  202.   *n = heap_n[1];
  203.   *a = heap_a[1];
  204.   *b = heap_b[1];
  205. #ifdef DEBUG
  206.   fprintf(stderr, "->	%ld, %u, %u\n", *n, *a, *b);
  207. #endif
  208.   parent = 1;
  209.   while (heap_n[parent] != DATA_MAX) {
  210.     child = parent << 1;
  211.     if (heap_n[child] > heap_n[child + 1])
  212.       child++;
  213.     heap_n[parent] = heap_n[child];
  214.     heap_a[parent] = heap_a[child];
  215.     heap_b[parent] = heap_b[child];
  216.     parent = child;
  217.   }
  218. #ifdef DEBUG_VOMIT
  219.   vomit_heap();
  220. #endif
  221.   return;
  222. }
  223.  
  224. /*
  225. DATA top_heap(void) {
  226. 	return heap_n[1];
  227. }
  228. */
  229.  
  230. #define VOMIT_LEVEL 15
  231.  
  232. void vomit_heap(void) {
  233.   PARA max, i;
  234.  
  235.   for (max = N_MAX - 1; heap_n[max] == DATA_MAX && max > 0; max--)
  236.     ;
  237.   fprintf(stderr, "vomit_heap:\n");
  238.   if (max < VOMIT_LEVEL) max = VOMIT_LEVEL;
  239.   i = 0;
  240.   while(i < max) {
  241.     fprintf(stderr, "heap[%u] %ld: (%u, %u) \n",
  242.             i,heap_n[i],heap_a[i],heap_b[i]);
  243.     i++;
  244.   }
  245.   return;
  246. }
  247.  
  248. /* end */
  249.  
Success #stdin #stdout #stderr 2.64s 126592KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
solution :
4118877
= 165^3 - 72^3
= 162^3 - 51^3
= 178^3 - 115^3
= 678^3 - 675^3
solution :
1412774811
= 1134^3 - 357^3
= 1155^3 - 504^3
= 1246^3 - 805^3
= 2115^3 - 2004^3
= 4746^3 - 4725^3
stderr
copy 
(time: 2 sec.)
https://ideone.com/KWQhAK
language:
C (gcc 8.3)
created:
6 years 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!