/*
2001/10 こだ割り数
coded by Isaku WADA
 ┌───────────────────────────┐
 │ ここにあげた整数は,                │
 │「左端からN桁で切ってできる数はすべてNで割りきれる」│
 │という性質を持つ。                  │
 │                           │
 │  7620543270               │
 │                           │
 │ 実際,たとえば762は3で,7620543は7で, │
 │7620543270は10で割りきれるのがわかる。  │
 │このような数を「こだ割り数」と呼ぶことにする。    │
 │最大のこだ割り数はいくつだろうか。          │
 │なお,左端の数字に0(ゼロ)は使えない。       │
 └───────────────────────────┘
 ┌───────────────────────────────┐
 │・プログラムの説明                      │
 │                               │
 │例えば、9桁で最大のこだ割り数を表示するプログラムは、再帰呼 │
 │び出しを使ってList1のように実現できます。探索の時 keta が2 │
 │の倍数、5の倍数、の10倍数かそうでないかによって増分 dx を │
 │変え、高速化しています。                   │
 │                               │
 │このプログラムを、最大のこだ割り数が求まるように改造するには、│
 │long の代わりに多倍長整数を使うようにし、if (keta==9) return; │
 │を取り除きます。                       │
 │                               │
 │■List1                           │
 │#include <stdio.h>                      │
 │long Max;                           │
 │                               │
 │void Sub(long curr)                      │
 │{                               │
 │  static int keta=1;                    │
 │  long next; int i,dx;                   │
 │                               │
 │  if (curr>Max) Max=curr;                  │
 │  if (keta==9) return;                   │
 │  keta++; next=curr*10;                   │
 │  dx=(keta%5?2:10)>>(keta&1);                │
 │  for (i=0;i<=9;i+=dx,next+=dx)               │
 │   if (next%keta==0) Sub(next);              │
 │  keta--;                          │
 │}                               │
 │                               │
 │int main(void)                        │
 │{                               │
 │  int i;                          │
 │                               │
 │  for (i=1;i<=9;i++) Sub((long)i);             │
 │  printf("%ld\n",Max); return 0;              │
 │}                               │
 └───────────────────────────────┘
 ┌───────────────────────────────┐
 │・感想                            │
 │                               │
 │プログラムの3分の2以上が、多倍長整数関係に占められています。│
 │しかし、チューンした割には、すっきりしたソースになりました。 │
 └───────────────────────────────┘
 Visual C++,Borland C++,LSI C,Turbo C,gcc で動作確認
*/

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

/*┌────────────────────┐
 │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

/*
 * 65536進法の多倍長整数(vint)
 * V_SIZE は最大桁数
 * x[0] は桁数
 * x[1〜x[0]] にリトルエンディアンで値が記録される
 * x[0] が0ならば0を表す
 * 参考文献:「コンピュータ・アルゴリズム事典」1987 技術評論社 
 *         第4章「多倍長計算」
 */
#define V_SIZE 6
typedef unsigned short uShort,vint[V_SIZE+1];

/*┌─────────────┐
 │整数を多倍長整数へ変換する│
 └─────────────┘*/
uShort*IntToVint(int n)
{
    static vint ret;

    if (n==0) ret[0]=0;
    else { ret[0]=1; ret[1]=(uShort)n; }
    return ret;
}

/*┌──────────────────────┐
 │多倍長整数を比較する(a<b:-1, a==b:0, a>b:1) │
 └──────────────────────┘*/
int CmpVint(vint a,vint b)
{
    int i;

    if (a[0]>b[0]) return 1;
    if (a[0]<b[0]) return-1;
    for (i=a[0];i>0&&a[i]==b[i];i--) ;
    if (i==0) return 0;
    if (a[i]>b[i]) return 1; else return-1;
}

/*┌──────────────┐
 │多倍長整数に整数を足す(x+=n)│
 └──────────────┘*/
void IncVint(vint x,int n)
{
    int i; unsigned long t;

    if (x[0]==0) { x[0]=1; x[1]=(uShort)n; return; }
    t=(unsigned long)x[1]+n; i=1;
    while (i<x[0]&&t>=65536L)
    { t-=65536L; x[i]=(uShort)t; i++; t=x[i]+1; }
    if (t<65536L) x[i]=(uShort)t;
    else if (i<V_SIZE)
    { x[i]=(uShort)(t-65536L); x[0]=(uShort)(i+1); x[x[0]]=1; }
    else { printf("Overflow at IncVint()\n"); exit(1); }
}

/*┌────────────────┐
 │多倍長整数に整数を掛ける(x=a*n) │
 └────────────────┘*/
void MulVint(vint x,vint a,int n)
{
    int i; unsigned long t=0;

    if (n==0) { x[0]=0; return; }
    for (i=1;i<=a[0];i++)
    { t+=(unsigned long)a[i]*n; x[i]=(uShort)(t&65535L); t>>=16; }
    if (t==0) x[0]=a[0];
    else if (a[0]<V_SIZE)
    { x[0]=(uShort)(a[0]+1); x[x[0]]=(uShort)t; }
    else { printf("Overflow at MulVint()\n"); exit(1); }
}

/*┌─────────────────┐
 │多倍長整数を整数で割った余り(a%n) │
 └─────────────────┘*/
int ModVint(vint a,int n)
{
    int i; unsigned long t=0;

    for (i=a[0];i>0;i--) { t=(t<<16)+a[i]; t%=n; }
    return(int)t;
}

/*┌──────────────────────┐
 │多倍長整数を整数で割る(a/=n)。返り値は(a%n) │
 └──────────────────────┘*/
int DivAndModVint(vint a,int n)
{
    int i; unsigned long t=0;

    for (i=a[0];i>0;i--)
    { t=(t<<16)+a[i]; a[i]=(uShort)(t/n); t%=n; }
    if (a[a[0]]==0) a[0]--;
    return(int)t;
}

/*┌──────────┐
 │多倍長整数を表示する│
 └──────────┘*/
void PrintVint(vint a)
{                                              
    static char buf[V_SIZE*5+1]; int i=V_SIZE*5; vint x;

    memcpy(x,a,sizeof x);
    do buf[--i]=(char)(DivAndModVint(x,10)+'0'); while (x[0]);
    printf("%s\n",&buf[i]);
}

vint Max;

/*┌─────────────────┐
 │再帰呼び出しをしながらパズルを解く│
 └─────────────────┘*/
void Sub(vint curr)
{
    static int keta=1; vint next; int i,dx;

    if (CmpVint(curr,Max)>0) memcpy(Max,curr,sizeof Max);
    keta++; MulVint(next,curr,10); dx=(keta%5?2:10)>>(keta&1);
    for (i=0;i<=9;i+=dx,IncVint(next,dx))
      if (ModVint(next,keta)==0) Sub(next);
    keta--;
}

/*┌───────┐
 │メインルーチン│
 └───────┘*/
int main(void)
{
    double StartTime=clock(); int i;

    for (i=1;i<=9;i++) Sub(IntToVint(i));
    PrintVint(Max);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}