记忆化搜索，因为要求最小的，肯定是从小到大，依次添加，那么通过bfs，队列貌似是最好的选择。因为很可能那个数爆long long，所以采用字符串存储，并记录余数，通过模拟除法的方式来写。
剪枝：因为后面添加的数都是一样的，所以相同的余数后面的过程都是一样的，所以我们需要通过一个数组优化。
注意：string和char数组的相互转写和除数和被除数分别为0的情况。
#include<cstdio> #include<algorithm> #include<cmath> #include<map> #include<iostream> #include<vector> #include<cstring> #include<queue> #include<string> using namespace std; int a[10]; struct node { string s; int res; }; int mark[5000]; int m,n; string bfs() { queue<node> q; string ss; for(int i=0;i<n;i++) { int x=a[i]%m; if(a[i]!=0&&x==0) { return ss+char(‘0‘+a[i]); } if(mark[x]) continue; node t; t.s=ss+char(‘0‘+a[i]); t.res=x; q.push(t); mark[x]=1; } node ans; while(!q.empty()) { node t=q.front(); q.pop(); for(int i=0;i<n;i++) { int xx=(t.res*10+a[i])%m; if(t.res*10+a[i]!=0&&xx==0) { return t.s+char(‘0‘+a[i]); } if(mark[xx]) continue; node g; g.res=xx; g.s=t.s+char(‘0‘+a[i]); q.push(g); mark[xx]=1; } } return ss+char(‘0‘); } int main() { // freopen("input.txt","r",stdin); while(scanf("%d%d",&m,&n)==2) { memset(mark,0,sizeof(mark)); for(int i=0;i<n;i++) { scanf("%d",&a[i]); } if(m==0) { printf("%d\n",m); continue; } sort(a,a+n); cout<<bfs()<<endl; } }
原文：http://www.cnblogs.com/acliang/p/4917940.html