/*
2003/07 2組の5乗数の和
coded by Isaku WADA

 ┌─────────────────────────────┐
 │ 650033は,3つの4乗数の和で2通りに表せる。4乗数とは,│
 │ある整数を4乗して得られる数のことである。        │
 │ 650033 = 11^4+12^4+28^4 = 14^4+23^4+24^4     │
 │ このような「3つの4乗数の和で2通りに表せる数」はほかに│
 │もたくさんある。では,「3つの5乗数の和で2通りに表せる数│
 │」を1つ見つけていただきたい。なお,ここでは正の数のみを扱│
 │うこととする。                      │
 └─────────────────────────────┘
 ┌────────┐
 │解答:1419138368│
 └────────┘
 ┌──────────────┬─────┬───────┐
 │コンパイラ         │実行時間 │ファイルサイズ│
 ├──────────────┼─────┼───────┤
 │Microsoft Visual C++ 6.0  │0.004406秒│ 36864 byte │
 │Microsoft Visual C++ .NET  │0.004250秒│ 45056 byte │
 │Borland C++ 5.5.1 for Win32 │0.004328秒│ 54272 byte │
 │gcc-2.953(djgpp)      │0.004670秒│ 109006 byte │
 │gcc-2.953(cygwin)      │0.004547秒│ 19884 byte │
 │LSI C-86 Ver 3.30 試食版  │0.102700秒│ 14010 byte │
 │Turbo C Ver 1.5(small model)│0.084600秒│ 11608 byte │
 ├──────────────┼─────┴───────┤
 │ CPU:Pentium4 2.52GHz │ OS:Windows XP    │
 └──────────────┴─────────────┘
 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │ 等式の各数値にsum=i^5+j^5+k^5=a^5+b^5+c^5のように名前を │
 │つけました。プログラムは最終的にi,j,k,a,b,cを変化させた6 │
 │重forループで解きます。                  │
 │ この6重forループを高速化するため、32768バイトのフラグの│
 │配列Flagsを用意しました。前準備としてi,j,kの3重forループ │
 │でsumを求め、その下位18ビットをlowとして求めておきます。 │
 │そして、lowを見て、対応するフラグを立てます。フラグを見な │
 │がら、3重ループ内で同じlowが複数回現れたならば、そのlowを│
 │配列LowTblに記録しておきます。同時に、そのlowに対応するiの│
 │値も配列Tbliに記録しておきます。             │
 │ メインの6重forループに入る前に、2分探索を可能にするた │
 │め、LowTblをTbliと共に昇順ソートしておきます。      │
 │ メインの6重forループの中でi,j,kが決まり、sumとその下位 │
 │18ビットlowが決まったら、2分探索で、LowTblを見て複数回現 │
 │れたかどうか調べます。もし、現れていなかったら無視しするこ│
 │とにより、枝刈りします。そして、lowに対応する全てのTbliを │
 │aとしてループを回します。さらに、その内側でb,cを制御変数と│
 │した2重forループを回します。               │
 │ a,b,cが決まって、a^5+b^5+c^5がsumと等しければ、このとき │
 │のsumが解答です。                     │
 ├─────────────────────────────┤
 │・感想                          │
 │                             │
 │ 32ビットコンパイラの場合、フラグの配列のサイズは524288バ│
 │イトで下位22ビットを見ます。ハッシングを使った3重forルー │
 │プの方法の方が、約2倍高速ですが、スモール・モデルでは実行│
 │できないので、現在の方法に落ち着きました。        │
 └─────────────────────────────┘*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/*┌─────┐
 │定数の宣言│
 └─────┘*/
#define POW 5                          /* 累乗数 */
#define MAX 66                         /* 探索範囲 */
#define BIT (sizeof(int)==2?18:22)     /* 下位ビット数 */
#define TBL (sizeof(int)==2?4718:1200) /* 表の大きさ */
#define MSK ((1L<<BIT)-1)              /* マスク */

/*┌─────┐
 │変数の宣言│
 └─────┘*/
unsigned long Pow[MAX+1];  /* 5乗数 */
char Flags[1U<<(BIT-3)];   /* 出現した下位ビットのフラグ */
unsigned long LowTbl[TBL]; /* 2回以上出た下位ビットの表 */
unsigned char Tbli[TBL];   /* 2回以上出た下位ビットのi */
int End;                   /* 2回以上出た下位ビットの総数 */

/*┌────────┐
 │配列を初期化する│
 └────────┘*/
void InitTable(void)
{
    int i,j,k; unsigned long sum,sumi,sumj,low;

    /* 5乗数を求める */    
    for (i=1;i<=MAX;i++) for (Pow[i]=1,j=0;j<POW;j++) Pow[i]*=i; 

    /* フラグと総数のクリア */
    memset(Flags,0,sizeof Flags); End=0;

    /* フラグをセットしながら LowTbl[] を求める */
    for (i=1;i<=MAX;i++) for (sumi=Pow[i],j=i;j<=MAX;j++)
     for (sumj=sumi+Pow[j],k=j;k<=MAX;k++) {
         sum=sumj+Pow[k]; low=sum&MSK;
         if (Flags[(unsigned)(low>>3)]&(1<<((unsigned)low&7))) {
             Tbli[End]=(unsigned char)i; LowTbl[End]=low; End++;
             /*if (sum==1419138368L) printf("TBL=%d\n",End);*/
             if (End==TBL) return;
         }else
             Flags[(unsigned)(low>>3)]|=1<<((unsigned)low&7);
     }
}

/*┌──────────────┐
 │LowTblとTbliを挿入ソートする│
 └──────────────┘*/
void Sort(void)
{
    int i,j; unsigned long x; unsigned char y;

    for (i=End-1;i>0;i--)
     if (LowTbl[i-1]>LowTbl[i]) {
         x=LowTbl[i-1]; y=Tbli[i-1]; j=i;
         do { LowTbl[j-1]=LowTbl[j]; Tbli[j-1]=Tbli[j]; j++; }
         while (j<End&&x>LowTbl[j]);
         LowTbl[j-1]=x; Tbli[j-1]=y;
     }
}

/*┌─────────────────────┐
 │パズルを解く。引数が0以外なら解を表示する│
 └─────────────────────┘*/
void Solve(int prn)
{
    int i,j,k,a,b,c,u; unsigned long sum,sumi,sumj,suma,sumb,low;
    
    for (i=1;i<=MAX;i++)
     for (sumi=Pow[i],j=i;j<=MAX;j++)
      for (sumj=sumi+Pow[j],k=j;k<=MAX;k++) {
          sum=sumj+Pow[k]; low=sum&MSK;
          for (a=0,b=End-1;a<b;) /* 2分探索 */
           if (LowTbl[c=(a+b)>>1]<low) a=c+1; else b=c;
          if (LowTbl[a]==low) {
              for (u=a-1;u>=0&&LowTbl[u]==low;u--) ;
              for (u++;u<End&&LowTbl[u]==low;u++)
               if ((a=Tbli[u])>i)
                for (suma=Pow[a],b=a;b<=MAX;b++)
                 for (sumb=suma+Pow[b],c=b;c<=MAX;c++)
                  if (sumb+Pow[c]==sum) {
                      if (prn) printf("%lu=%d %d %d:%d %d %d\n",
                                       sum, i, j, k, a, b, c);
                      return;
                  }
          }
      }
    printf("%sMAXが小さい\n",End==TBL?"TBLか":""); exit(1);
}

/*┌────────────────────┐
 │MS-DOS コンパイラ用のシンプルな clock() │
 └────────────────────┘*/
#if CLOCKS_PER_SEC == 1
#undef CLOCKS_PER_SEC
#endif
#ifndef CLOCKS_PER_SEC
#define CLOCKS_PER_SEC 1000
#include <dos.h>
static long clock(void) {
    union REGS t; t.h.ah=0x2c; intdos(&t,&t);
    return t.h.dl*10L+t.h.dh*1000L+t.h.cl*60000L+t.h.ch*3600000L;
}
#endif

/*┌────────┐
 │メイン・ルーチン│
 └────────┘*/
int main(int argc,char**argv)
{
    double StartTime=clock(); int i,num;

    if (argc==2) num=atoi(argv[1]); else num=1;
    for (i=0;i<num;i++) { InitTable(); Sort(); Solve(i==0); }
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}