做題感悟：
這道題是在學長講完取余的方法後才做的，開始用的以前用的方法，結果超內存，然後用了 C++ 的 string 類後又超時，真無語！經過這一題，明顯發現自己掌握的知識太少了。
題意：
給你一個 n ，讓你找它的倍數，要有最少的不同的數字，如果不同的數字一樣，輸出數小的那個。
解題思路：
首先要用到超級密碼那題的取餘思想，其次還有一點，任何一個數都可以用兩種不同的數字表示倍數（數論中的定理）。用 string 類時廣搜到結果時要回溯的方法（具體看代碼，提交用C++）。
代碼：
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<string>
#include<queue>
using namespace std ;
#define MX 65536
int n,num,mx ;
int g[5] ;
bool vis[MX],flag ;
struct zhang
{
int x,m,cnt,pre ;// pre 記錄父親節點
}q[MX] ;
string str,key ;
void gettemp(int k) // 回溯複製到 str ，如果不用會超時
{
if(k==-1)
return ;
gettemp(q[k].pre) ; // 找父親
str+=(q[k].x+'0') ;
return ;
}
int bfs()
{
int head=0,tail=-1 ;
memset(vis,false,sizeof(vis)) ;
for(int i=0 ;i<num ;i++)
{
if(!g[i]) continue ;
zhang current ;
current.pre=-1 ;
current.x=g[i] ; // 存放的數
current.m=g[i]%n ; // 存餘數
current.cnt=1 ; // 記錄個數
vis[current.m]=true ;
q[++tail]=current ;
}
while(head<=tail)
{
int h=head ;head++ ;
if(q[h].cnt>mx) // 當大於最少個數時不進行下去
continue ;
if(!q[h].m) // 找到滿足的解
{
str="" ;
gettemp(h) ;
if(q[h].cnt<mx)
{
key=str ;
mx=q[h].cnt ;
}
else if(q[h].cnt==mx)
{
if(str<key)
key=str ;
}
return true ;
}
for(int i=0 ;i<num ;i++)
{
int mod=(q[h].m*10+g[i])%n ;
if(vis[mod]) continue ;
vis[mod]=true ;
zhang tep ;
tep.m=mod ; tep.cnt=q[h].cnt+1 ;
tep.x=g[i] ; tep.pre=h ; // 記錄前一個值，為了不超時
q[++tail]=tep ;
}
}
return false ;
}
int main()
{
int i,j ;
while(scanf("%d",&n)!=EOF)
{
if(!n) break ;
num=1 ;mx=9999999 ;flag=false ;
key="" ;
for(i=1 ;i<=9 ;i++)
{
g[0]=i ;
if(bfs())
flag=true ;
}
if(flag)
{
cout<<key<<endl ;
continue ;
}
num=2 ;
for(i=0 ;i<=9 ;i++)
{
g[0]=i ;
for(j=i+1 ;j<=9 ;j++)
{
g[1]=j ;
bfs() ;
}
}
cout<<key<<endl ;
}
return 0 ;
}