/**********************************************************************/
/*                                     Ｃmagazine 1996.10 電脳クラブ  */
/*   標    題   三乗の参上                                            */
/*                                                                    */
/*                 3     3     3     3     3    3     3    3          */
/*   解    答   678 - 675 = 178 - 115 = 165 - 72 = 162 - 51 = 4118877 */
/*                                                                    */
/*   使用機種   FMR-50NL (i486sx 25MHz)                               */
/*   Ｏ    Ｓ   MS-DOS Ver6.2                                         */
/*   コンパイラ LSI C-86 Ver3.30C(試食版)                             */
/*   実行時間   0.22 秒                                               */
/*                                                                    */
/**********************************************************************/
#include <stdio.h>

#define  AMAX    1290 /* LONG_MAX(2,147,483,647)の3乗根               */
#define  HSIZE  56010 /* 出現数カウンタサイズ(メモリの許す限り大きく) */

long san[AMAX+1];     /* ３乗値テーブル */
char HASH[HSIZE];     /* 出現数カウンタ */

void main(void)
{
    int  a, b, c, d, e, f, g, h, ra, rb, rc, rd, re, rf, rg, rh;
    long p, x, rx = AMAX * AMAX * AMAX - (AMAX-1)*(AMAX-1)*(AMAX-1);

    /* a,bを生成し3乗差xを算出 */
    for (a=1; a<=AMAX; a++) {
      san[a] = a * a * a;                      /* ３乗値テーブル作成  */
      if (san[a]-san[a-1] > rx) break;         /* 終了判定(rx最小決定)*/
      for (b=a-1; b; b--) {
        if ((x=san[a]-san[b]) > rx) break;     /* rxを越えるxは無視   */

        if (++HASH[x % HSIZE] < 4) continue;   /* 枝刈り(xの必要条件) */

        /* 3乗差がxとなるc,dを降方に探す */
        for (c=a-1, d=b-1; (p=san[c]-x)>=27; c--) {
          while (san[--d] > p);                /* pは,求めるdの3乗値  */
          if (san[d] < p) continue;

          /* 3乗差がxとなるe,fを降方に探す */
          for (e=c-1, f=d-1; (p=san[e]-x)>=8; e--) {
            while (san[--f] > p);
            if (san[f] < p) continue;

            /* 3乗差がxとなるg,hを降方に探す */
            for (g=e-1, h=f-1; (p=san[g]-x)>=1; g--) {
              while (san[--h] > p);
              if (san[h] < p) continue;

              /* a〜h,xの記録更新(重複値をチェックしてから) */
              if (c!=b && e!=b && e!=d && g!=b && g!=d && g!=f) {
                ra=a; rb=b; rc=c; rd=d; re=e; rf=f; rg=g; rh=h; rx=x;
              }
            }
          }
        }
      }
    }
    /* 結果の表示 */
    if (a <= AMAX)
      printf("%d-%d=%d-%d=%d-%d=%d-%d=%ld",ra,rb,rc,rd,re,rf,rg,rh,rx);
    else
      printf("残念ですが,long値の範囲では求められません。");
}

/************************** ( プログラムの説明、感想 ) *****************

・プログラムの説明

    long値の範囲で求められると仮定すると,LONG_MAXの3乗根(AMAX)が求め
  る変数(a〜h)の最大値となります。また,得られた3乗差xが最小であること
  を立証出来るxの最大値は,AMAXと(AMAX-1)の3乗差までなので,この値をxの
  最小記録(rx)に設定し,この値より大きいxは探索を放棄します。
    さて,for文を2重にネストしてa,bを生成し,その3乗差xを算出します。こ
  こで,xがrxを越えていれば調べる必要がなく,さらに,後述する枝刈りでふ
  るいにかけ,次に3乗差がxとなるc,dをaより降方に向かって探索し,同様に
  してg,hの組合せまで見つかれば,解の候補として記録を更新します。
    終了判定は,変数の最大値aと(a-1)の3乗差がrxを越えた時点でrxが最小
  であることが立証され終了となります。
    枝刈り法は,先ず空きメモリに目一杯大きな配列(要素数HSIZE)を確保しま
  す。a,bを生成して3乗差xを算出した際,xをHSIZEで割った余り値の出現回数
  をこの配列でカウントすると,カウント数が4未満なら少なくともまだ求め
  るxの【必要条件】を満たしていないので,無駄な深追いを避けられます。

・感  想

    HSIZEの値は大きい程効果的ですが,3乗値を割った余りが一様に分布しな
  い4,7,8,9,..等の倍数だと効果が薄れてしまう様です。そこで,私の場合は
  30(=2*3*5)の素数倍から適当なものを選んでみました。

***********************************************************************/