/*
2004/2 肩のせ文字の誤植
coded by Isaku WADA
 ┌─────────────────────────────┐
 │ 「3^4*425」はいうまでもなく,「3の4乗に425を掛ける」と │
 │いう意味であるが,これを間違えて34425と書いても,結果とし │
 │て同じになる。                      │
 │ 3^4*425=34425                      │
 │ このように,「a^b*c」という式で,肩に乗せておくべき数を │
 │間違えて並べて書いても結果として同じになるものの中で,上 │
 │式の右辺が6桁で成立するものをすべてお答えいただきたい。 │
 │なお,すでに成立している式のcの最後に0を付加したもの(上の │
 │例では,3^4*4250=344250も,その解の1つであることは明白で │
 │ある。a,b,cは何桁の数であってもよい。また,各数の左端の数 │
 │字に0はこないこととする。                 │
 └─────────────────────────────┘
 ┌────────┐
 │解答:     │
 │3^4*4250=344250 │
 │31^2*325=312325 │
 │49^2*205=492205 │
 └────────┘
 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │ a^b*cのaが1だと仮定すると計算結果の桁が短くなるので、aは│
 │2以上であることがわかります。同様にbも2以上であることがわ │
 │かります。また、bが2以上であることから、aは3桁以上にならな│
 │いこともわかります。さらに、2の14乗が16384であることから、│
 │aが2の時はbは13以下で、3の10乗が59049であることから、aが3 │
 │以上の時はbは1桁であることがわかります。         │
 │                             │
 │ aとbが与えられた時に、x=a^bとし、さらにaとbの桁数によっ │
 │て、以下の表に従ってyを求めます。             │
 │┌───┬───┬─────────┐          │
 ││aが1桁│bが1桁│y=a*100000+b*10000│          │
 │├───┼───┼─────────┤          │
 ││aが1桁│bが2桁│y=a*100000+b*1000 │          │
 │├───┼───┼─────────┤          │
 ││aが2桁│bが1桁│y=a*10000+b*1000 │          │
 │└───┴───┴─────────┘          │
 │                             │
 │ 例えばa=3、b=4ならばx=81でy=340000となります。もし、aとb│
 │が解答ならばx*c=y+cが成立するcが存在します。この方程式をc │
 │について解くと、c=y/(x-1)となります。           │
 │                             │
 │ プログラムはaを2から99まで変化させ、bを2から13まで変化さ│
 │せる2重forループで解を探します。その中でy%(x-1)が0の場合、│
 │c=y/(x-1)によりcを求め、cが正しい桁数ならば、解が得られた │
 │として表示します。枝刈りとして、xの桁数がaとbの桁数の和に │
 │1を足したものを超えたときはbのforループを抜けます。   │
 │                             │
 ├─────────────────────────────┤
 │・感想                          │
 │                             │
 │ いくら桁を増やしてもaとbの組み合わせが限られているので、│
 │3種類の解しか見つかりませんでした。ただ、9桁にしても、プロ│
 │グラムを工夫したおかげで、計算速度はほとんど落ちませんでし│
 │た。                           │
 └─────────────────────────────┘
 ┌──────────────┬───────┬───────┐
 │コンパイラ         │実行時間   │ファイルサイズ│
 ├──────────────┼───────┼───────┤
 │Microsoft Visual C++ 6.0  │0.000003500 秒│ 36864 byte │
 │Microsoft Visual C++ 2003  │0.000003250 秒│ 45056 byte │
 │Borland C++ 5.5.1 for Win32 │0.000004234 秒│ 53248 byte │
 │gcc-2.953(djgpp)      │0.000003352 秒│ 108357 byte │
 │gcc-2.953(cygwin)      │0.000003485 秒│ 19068 byte │
 │LSI C-86 Ver 3.30 試食版  │0.000014550 秒│ 13418 byte │
 │Turbo C Ver 1.5(small model)│0.000069210 秒│ 10922 byte │
 ├──────────────┼───────┴───────┤
 │ CPU:Pentium4 2.52GHz │ OS:Windows XP      │
 └──────────────┴───────────────┘*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*┌──────┐
 │右辺の最小数│
 └──────┘*/
#define K 100000L

/*┌────────┐
 │パズルを1回解く│
 └────────┘*/
void Solve(int print)
{
    unsigned a,b,x,maxB=14,maxX=1000;
    unsigned long c,y,uhenA,minC=K/100,maxC=K/10,baseA=K;

    for (a=2;a<100;a++) {
        if (a==3) { maxX=1000; minC=K/100; maxC=K/10; }
        else if (a==10)
        { baseA=K/10; maxX=10000; minC=K/1000; maxC=K/100; }
        uhenA=a*baseA; x=a;
        for (b=2;b<maxB;b++) {
            if (b==10) { maxX=10000; minC=K/1000; maxC=K/100; }
            x*=a;                            /* x=a^b */
            if (x>=maxX) { maxB=b; break; }  /* 枝刈り */
            y=uhenA+b*maxC;
            if (y%(x-1)==0) {
                c=y/(x-1);                   /* x*c==y+c を解く*/
                if (c>=minC&&c<maxC)
                 if (print) printf("%u^%u*%lu=%lu\n",a,b,c,y+c);
            }
        }
    }
}

/*┌────────────────────┐
 │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(); long i,num;

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