題意：

給出一個n和m個數

?

求一個最小的數 1 為n的倍數 ?2 沒有這m個數字中的任意一個

?

123%n = ((((1%n)*10+2)%n)*10+3)%n

如果? ? ?a%n==b%n? ? ?

那么? ? (a+x)%n==(b+x)%n

?

這樣就可以剪枝了? ?之前取模n出現過的后來再出現就可以不要了 ? ??

?

例如 ?

A%n==B%n 且 A<B 那么B就不用處理了

#include<cstdio> #include<cstring> #include<vector> #include<queue> #include<algorithm> #define LL __int64 using namespace std;const int MAXN = 11111;struct Node {vector <int> num;int c; } tmp;queue <Node> q;int have[MAXN]; int vis[11];int n;void bfs() {while(!q.empty()) q.pop();memset(have,0,sizeof(have));for(int i = 1;i < 10;i++)if(!vis[i]){if(have[i%n]) continue;tmp.num.clear();tmp.num.push_back(i);tmp.c = i%n;q.push(tmp);have[i%n] = 1;}while(!q.empty()){Node cur = q.front();if(cur.c == 0) break;q.pop();for(int i = 0;i < 10;i++){if(vis[i]) continue;int tt = (cur.c*10+i)%n;if(!have[tt]){have[tt] = 1;tmp.num.clear();for(int j = 0;j < cur.num.size();j++)tmp.num.push_back(cur.num[j]);tmp.num.push_back(i);tmp.c = tt;q.push(tmp);}}}if(!q.empty()){for(int i = 0;i < q.front().num.size();i++)printf("%d",q.front().num[i]);puts("");}else puts("-1"); }int main() {int m;int cas = 0;while(~scanf("%d%d",&n,&m)){memset(vis,0,sizeof(vis));for(int i = 0;i < m;i++){int a;scanf("%d",&a);vis[a] = 1;}printf("Case %d: ",++cas);bfs();}return 0; } View Code

?

轉載于:https://www.cnblogs.com/bxd123/p/10994241.html

總結

以上是生活随笔為你收集整理的Yet Another Multiple Problem 同余定理 bfs的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。