稍微有点不一样 这次衡量的第一标准是位数的多少 第二标准才是数的大小
这里必须有一个 数论的 知识 不然不好写（I hate number theroy ……
对于任意的整数n，必然存在一个由不多于两个的数来组成的一个倍数。（之前写过数位BFS的应该可以理解
因为a，aa，aaa……取n+1个，则必有两个模n余数相同，相减即得n的倍数m。而m只由a、0组成。(这可以说是最糟的情况
所以只要先枚举所有的 1-9 的数 如果不存在 再枚举两个数的情况 （一直很奇怪网上的题解 0-9 不是有 45种情况么…………
还有 。。。沃特么也是SB 被自己坑到了 我还以为必须是他给的数 的位数作为范围 因为样例就是这样的…… 结果WA了好几发
AC Code
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
const int maxn=65540;
const int inf=0x3f3f3f3f;
int n,k,num[11],a[5];
char ch[3];
bool vis[maxn],flag[11];
string curans,ans;
struct node
{
char ch;
int pre,mod;
}que[maxn*10];
void getstr(int x)
{
if(que[x].pre!=-1)
getstr(que[x].pre);
curans+=que[x].ch;
}
bool bfs(int kk)
{
memset(vis,false,sizeof vis);
int l=1,r=1;
for(int i=0;i<kk;i++) if(a[i])
{
que[r].pre=-1;
vis[que[r].mod=a[i]%n]=true;
que[r].ch=a[i]+'0';
r++;
}
while(l<r)
{
for(int i=0;i<kk;i++)
{
int tmp=que[r].mod=(que[l].mod*10+a[i])%n;
if(!vis[tmp])
{
vis[tmp]=true;
que[r].pre=l;
que[r].ch=a[i]+'0';
if(tmp==0)
{
getstr(r);
return true;
}
r++;
}
}
l++;
}
return false;
}
bool cmp(const string& a,const string &b)
{
if(a.size()==b.size()) return a<b;
return a.size()<b.size();
}
int main()
{
while(scanf("%d",&n),n)
{
if(n<=11)//11之前直接输出 可以减少bfs的判断
{
printf("%d\n",n);
continue;
}
ans="";
bool wokao=false;
for(int i=1;i<10;i++)
{
a[0]=i;
curans="";
if(bfs(1))
if(!wokao||cmp(curans,ans))//大小关系是未知的 必须加以判断
{
wokao=true;
ans=curans;
}
}
if(wokao)
cout<<ans<<endl;
else
{
for(int i=0;i<10;i++)
for(int j=i+1;j<10;j++)
{
a[0]=i,a[1]=j;
curans="";
if(bfs(2))
if(!wokao||cmp(curans,ans))
{
wokao=true;
ans=curans;
}
}
cout<<ans<<endl;
}
}
return 0;
}