111 lines
2.7 KiB
C++
111 lines
2.7 KiB
C++
#include<stdio.h>
|
|
const int N = 65536;
|
|
const int M = N+N;
|
|
int x[2][N]={0},q[M]={0},p[M]={0};
|
|
int bfs(int a,int b,int n,int t)
|
|
{
|
|
int fr=0,r=1,i=0;
|
|
char f[N]={0};
|
|
q[0]=0;
|
|
if (a==0)
|
|
{
|
|
fr=2;
|
|
q[2]=b;
|
|
r=3;
|
|
f[0]=1;
|
|
p[2]=0;
|
|
}
|
|
while(fr<r)
|
|
{
|
|
if (f[q[fr]]==1)
|
|
{
|
|
fr++;
|
|
continue;
|
|
}
|
|
f[q[fr]]=1;
|
|
q[r]=(q[fr]*10+a)%n;
|
|
p[r]=fr;
|
|
if (q[r]==0)
|
|
break;
|
|
r++;
|
|
q[r]=(q[fr]*10+b)%n;
|
|
p[r]=fr++;
|
|
if (q[r]==0)
|
|
break;
|
|
r++;
|
|
}
|
|
if (fr<r)
|
|
{
|
|
for (i=0;r!=0;i++)
|
|
{
|
|
if (r%2==1)
|
|
x[t][i]=a;
|
|
else x[t][i]=b;
|
|
r=p[r];
|
|
}
|
|
return i-1;
|
|
}
|
|
return -1;
|
|
}
|
|
int main()
|
|
{
|
|
int n,d[10],c,i,j,k,m,t;
|
|
scanf("%d",&n);
|
|
while (n!=0)
|
|
{
|
|
d[0]=n;
|
|
c=0;
|
|
for (i=1;i<10;i++)
|
|
{
|
|
j=i;
|
|
d[i]=1;
|
|
while (d[i]<n && j%n!=0)
|
|
{
|
|
j=j%n*10+i;
|
|
d[i]++;
|
|
}
|
|
if (d[i]<d[c])
|
|
c=i;
|
|
}
|
|
if (c!=0)
|
|
{
|
|
for (j=d[c];j>0;j--)
|
|
printf("%d",c);
|
|
}
|
|
else{
|
|
m=n;
|
|
t=0;
|
|
for (i=0;i<10;i++)
|
|
{
|
|
for (j=i+1;j<10;j++)
|
|
{
|
|
c=bfs(i,j,n,t);
|
|
if (c!=-1 && c<m)
|
|
{
|
|
t=1-t;
|
|
m=c;
|
|
}
|
|
else if (c==m)
|
|
{
|
|
for (k=m;k>=0;k--)
|
|
{
|
|
if (x[t][k]<x[1-t][k])
|
|
{
|
|
t=1-t;
|
|
break;
|
|
}
|
|
else if (x[t][k]>x[1-t][k])
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
for (i=m;i>=0;i--)
|
|
printf("%d",x[1-t][i]);
|
|
}
|
|
printf("\n");
|
|
scanf("%d",&n);
|
|
}
|
|
return 0;
|
|
}
|