简单BFS + 大数取模的应用
因为n最大10000 暴搜一遍即可
#include<cstdio> #include<cstring> #include<queue> #include<stack> using namespace std; const int MAXN = 10007; struct node { int v,m,pre; void init(int tv,int tm,int tpre) { v = tv, m = tm, pre = tpre; } }e[MAXN]; bool exist[MAXN]; bool enable[10]; int main() { int n,m,id=0; while(~scanf("%d%d",&n,&m)) { memset(enable,0,sizeof(enable)); int i,x; for(i=0;i<m;i++) { scanf("%d",&x); enable[x] = true; } printf("Case %d: ",++id); memset(exist,0,sizeof(exist)); bool bans = false; int ent=0; queue<int> q; e[ent].init(0,0,-1); q.push(ent ++); while(!q.empty()) { int u=q.front(); q.pop(); for(i=0;i<10;i++) { if( !enable[i] ) { if(e[u].pre == -1 && i == 0) { continue; } int tm = (e[u].m * 10 + i ) % n; if(tm == 0) { stack<int> answer; answer.push(i); while( e[u].pre != -1) { answer.push(e[u].v); u = e[u].pre; } while(!answer.empty()) { putchar('0' + answer.top()); answer.pop(); } puts(""); bans = true; break; } if( !exist[tm] ) { e[ent].init(i,tm,u); q.push(ent ++); exist[tm] = true; } } } if(bans) { break; } } if(!bans) { puts("-1"); } } return 0; }