做题感悟：做了杭电上的两个题目，再做这个真是 so easy ！但是还要写一下的，用第二种方法很不熟练。。。
解题思路：还是用取余的思想，每次都将余数乘 10 再加 上相应的数，0 要特判一下。
代码1：
#include<stdio.h>
#include<iostream>
#include<string>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std ;
int n ;
bool vis[300] ; // 标记余数是否相同
struct zhang
{
int x,num ;
string str ; // 这个很好用
} ;
int bfs()
{
queue<zhang>q ;
zhang curt,next ;
memset(vis,false,sizeof(vis)) ;
curt.x=0 ;
curt.str="" ;
curt.num=0 ;
q.push(curt) ;
while(!q.empty())
{
curt=q.front() ;
q.pop() ;
if(curt.num>100) continue ;
for(int i=0 ;i<2 ;i++)
{
next=curt ;
next.num+=1 ;
next.x=next.x*10+i ;
if(!next.x) continue ;
if(next.x%n==0)
{
next.str+=(48+i) ;
next.str+='\0' ;
cout<<next.str<<endl ;
return true ;
}
next.x=next.x%n ;
if(vis[next.x]) continue ;
vis[next.x]=true ;
next.str+=(48+i) ;
q.push(next) ;
}
}
return false ;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
if(!n) break ;
bfs() ;
}
return 0 ;
}
代码2：
#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
#define MX 5000
using namespace std ;
int n ;
bool vis[300] ;
struct zhang
{
int x,m,pre,num ;
}q[MX];
void print(int k) // 输出 不用string 存数
{
if(k==-1)
return ;
print(q[k].pre) ;
printf("%d",q[k].x) ;
}
int bfs()
{
zhang curt,next ;
int start=-1,head=0 ;
memset(vis,false,sizeof(vis)) ;
curt.x=1 ;
curt.num=1 ;
curt.pre=-1 ;
if(n==1)
{
cout<<1<<endl ;
return true ;
}
vis[1]=true ;
curt.m=1 ;
q[++start]=curt ;
while(head<=start)
{
int h=head ;head++ ;
curt=q[h] ;
if(!curt.m)
{
print(h) ;
printf("\n") ;
return true ;
}
if(curt.num>100) continue ;
for(int i=0 ;i<2 ;i++)
{
next=curt ;
next.m=next.m*10+i ;
if(!next.m) continue ;
next.m=next.m%n ;
if(vis[next.m]) continue ;
vis[next.m]=true ;
next.x=i ;
next.num+=1 ;
next.pre=h ;
q[++start]=next ;
}
}
return false ;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
if(!n) break ;
bfs() ;
}
return 0 ;
}