Yet Another Multiple Problem 同余定理 bfs-白红宇

Yet Another Multiple Problem 同余定理 bfs

阅读量：5066 次

发布时间：2019-06-12

本文共 1449 字，大约阅读时间需要 4 分钟。

　　题意：

给出一个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
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define LL __int64using namespace std; const int MAXN = 11111; struct Node{    vector 
           
             num; int c;} tmp; queue 
            
              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;}