/*
2002/06 運のいい分数
coded by Isaku WADA
 ┌───────────────────────────┐
 │ 「分母と分子にある同じ数字を消す」という間違った約分│
 │を,Fig.1の分数に対して行った。すると運のいいことに,│
 │正しく約分した値と同じになったではないか。この「運のい│
 │い分数」は無限にあるので,下のような条件を付ける。  │
 │ (1)分母と分子で同じ数字があればそのペアは必ず消す │
 │ (2)消されるペアは,分母と分子に1文字ずつしか入って│
 │   いない。つまり,消すペアは一意に決まり,また,同│
 │   じ数字で複数のペアが存在することもない     │
 │ (3)最終的に分母分子がそれぞれ一桁でできた,1未満の│
 │   既約分数となる                 │
 │ (4)数字の0(ゼロ)は使わない            │
 │ (5)正の数のみを扱う                │
 │ この条件で,上記の間違った約分を行った結果が正しく約│
 │分した値と同じになる「運のいい分数」は何通りあるだろう│
 │か。                         │
 │                           │
 │   Fig.1 分数                  │
 │       //                  │
 │      187    1             │
 │      ─── = ───            │
 │      748    4             │
 │      / /                  │
 └───────────────────────────┘
 ┌────────┐
 │解答:322通り│
 └────────┘
 ┌──────────────┬─────┬───────┐
 │コンパイラ         │実行時間 │ファイルサイズ│
 ├──────────────┼─────┼───────┤
 │Microsoft Visual C++ .NET  │ 0.3218 秒│ 45056 byte │
 │Borland C++ 5.5 for Win32  │ 0.3781 秒│ 54272 byte │
 │gcc-2.953(djgpp)      │ 0.2637 秒│ 109853 byte │
 │gcc-2.953(cygwin)      │ 0.2687 秒│ 20706 byte │
 │LSI C-86 Ver 3.30 試食版  │ 1.5050 秒│ 14250 byte │
 │Turbo C Ver 1.5(small model)│ 5.5500 秒│ 11836 byte │
 ├──────────────┼─────┴───────┤
 │ CPU:Pentium4 2.52GHz │   OS:Windows XP   │
 └──────────────┴─────────────┘
 ┌──────────────────────────────┐
 │・プログラムの説明                     │
 │                              │
 │最終的に分母分子がそれぞれ一桁でできた1未満の既約分数となる│
 │という条件があります。この条件を満たした既約分数を全て列挙し│
 │てみると、1/2,1/3...8/9などの27個の分数が得ら│
 │れます。プログラムは、この27個の分数全てを元に処理を行いま│
 │す。この時、ここで選ばれた分数の分子をnume0とし、分母をdeno0│
 │とします。                         │
 │                              │
 │そして、27個の分数それぞれについて、nume0でもdeno0でもなく│
 │、0でもない7つの数字を求めます。この集合をReductSetとしま │
 │す。これは約分の時に消える数字の候補です。         │
 │                              │
 │そして、この集合から1個以上の数字を選ぶ全127通りの方法に│
 │ついて調べます。さらに、この方法で選んだ集合にnume0を足した │
 │集合をNumeSetとし、deno0を足した集合をDenoSetとします。   │
 │                              │
 │つぎに、NumeSetの全ての順列について調べます。そして、選んだ │
 │順列を十進法に基づき値に変換します。これを約分前の分子とし │
 │numeとします。つぎに、最初に選んだ既約分数を参照して、対応す│
 │る約分前の分母を求めます。これをdenoとします。具体的には  │
 │deno=nume/nume0*deno0とします。denoを計算する前にnumeをnume0│
 │で割った余りが0でない場合は無視します。この分母denoを十進法│
 │に基づき各桁に分解し、得られた数字の集合と、DenoSetが一致す │
 │れば、解としてnumeを記録します。              │
 │                              │
 │解は最初に選んだ既約分数ごとに溜めてゆき、その既約分数の処理│
 │が終わった時に、小さい順にソートして出力します。      │
 ├──────────────────────────────┤
 │・感想                           │
 │                              │
 │約分前の分子・分母はそれぞれ最大で8桁なので、31bit整数で間 │
 │に合いました。これは助かります。1/4など、既約分数そのもの│
 │も「運のいい分数」に含めるかどうか迷いましたが、約分ができな│
 │いので含めませんでした。                  │
 └──────────────────────────────┘
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZEOF(X) (sizeof(X)/sizeof(X[0]))

/*┌─────────────────┐
 │Nume0[i]/Deno0[i] 最終的な既約分数│
 └─────────────────┘*/
int Nume0[]={1,1,1,1,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,5,5,5,5,6,7,7,8};
int Deno0[]={2,3,4,5,6,7,8,9,3,5,7,9,4,5,7,8,5,7,9,6,7,8,9,7,8,9,9};

int  ReductSet[7]; /* 約分で消える数字の候補の集合 */
int  NumeSet[8];   /* 分子に現れる数字の集合 */
int  DenoSet[8];   /* 分母に現れる数字の集合 */
int  Flag[10];     /* 分母の数字が全て使われたかどうか */
long Log[50];      /* 解を溜めておく場所 */
int  LogSize;      /* 現在の既約分数での解の数 */
int  Count;        /* 解の総数 */

/*┌───────────────┐
 │挿入ソート(解の表示の時に使う)│
 └───────────────┘*/
void InsertSort(long*x,int n)
{
    int i,j; long k;

    for (i=n-1;i>0;i--)
     if (x[i-1]>x[i]) {
         k=x[i-1]; j=i;
         do { x[j-1]=x[j]; j++; } while (j<n&&k>x[j]);
         x[j-1]=k;
     }
}

/*┌─────────────────────────┐
 │x[] を辞書順で次の順列に設定する。最後なら0を返す│
 │順序関係のみ見ているので、連続していなくてもOK  │
 └─────────────────────────┘*/
int NextPermutation(int*x,int n)
{
    int i,j,k;

    for (i=n-2;i>=0&&x[i]>=x[i+1];i--) ;
    if (i==-1) return 0;
    for (j=n-1;x[i]>=x[j];j--) ;
    k=x[i]; x[i]=x[j]; x[j]=k; i++;
    for (j=n-1;j>i;j--,i++) { k=x[i]; x[i]=x[j]; x[j]=k; }
    return 1;
}

/*┌───────────────────────┐
 │溜まった解を昇順に表示する          │
 │80 カラムを超えようとしたら、自動的に改行する │
 └───────────────────────┘*/
void Print(int nume0,int deno0)
{
    int i,col; char bf[32];

    InsertSort(Log,LogSize);
    col=printf("(%d/%d)",nume0,deno0);
    for (i=0;i<LogSize;i++) {
        if (col+sprintf(bf," %ld/%ld",Log[i],Log[i]/nume0*deno0)>79)
        { printf("\n"); col=0; }
        col+=printf(bf);
    }
    printf("\n");
}

/*┌───────────────┐
 │分子の順列が与えられた後の処理│
 └───────────────┘*/
void Sub(int size,int nume0,int deno0)
{
    long deno,nume,r; int i,digit;

    /* 約分前の分子を求める */
    for (nume=i=0;i<size;i++) nume=nume*10+NumeSet[i];

    /* 割り切れるかどうかを見てから、約分前の分母を求める */
    if (nume0==1) deno=nume*deno0;
    else if (nume%nume0) return; else deno=nume/nume0*deno0;

    /* 分母のフラグを設定する */
    for (i=0;i<=9;i++) Flag[i]=0;
    for (i=0;i<size;i++) Flag[DenoSet[i]]=1;

    /* 約分前の分母を各桁に分解してフラグと照らし合わせる */
    for (r=deno;r;r/=10)
     if (Flag[digit=(int)(r%10)]) Flag[digit]=0; else return;
    for (i=0;i<=9;i++) if (Flag[i]) return;

    /* ログに記録する */
    if (LogSize>=SIZEOF(Log))
    { printf("\aSorry:size of 'Log' is too small\n"); exit(1); }
    Log[LogSize++]=nume;
}

/*┌────────┐
 │一回パズルを解く│
 └────────┘*/
void Solve(void)
{
    int stage,size,comb,nume0,deno0,i;

    for (Count=stage=0;stage<SIZEOF(Nume0);stage++) {
        LogSize=size=0; nume0=Nume0[stage]; deno0=Deno0[stage];

        /* 約分で消える予定の数字を登録する */
        for (i=1;i<=9;i++)
         if (i!=nume0&&i!=deno0) ReductSet[size++]=i;

        /* 1つ以上の集合の全ての組み合わせを調べる */
        for (comb=1;comb<128;comb++) {

            /* 分母分子の集合に組み合わせから選んだ数字を追加する */
            for (size=i=0;i<7;i++) if ((1<<i)&comb)
            { NumeSet[size]=DenoSet[size]=ReductSet[i]; size++; }

            /* 分母の集合にdeno0を追加する */
            DenoSet[size]=deno0;

            /* 分子の集合にnume0を追加する */
            /* 昇順の順列になるように適切な位置に挿入する */
            for (i=size;i>0&&NumeSet[i-1]>nume0;i--)
                NumeSet[i]=NumeSet[i-1];
            NumeSet[i]=nume0; size++;

            do /* 順列を処理する */
                Sub(size,nume0,deno0);
            while (NextPermutation(NumeSet,size));
        }
        if (LogSize) { Print(nume0,deno0); Count+=LogSize; }
    }
    printf("解の総数 %d\n",Count);
}

/*┌────────────────────┐
 │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++) Solve();
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}