hdu1664 bfs+余数判重-白红宇

hdu1664 bfs+余数判重

阅读量：5462 次

发布时间：2019-06-16

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

input

n　　　　不超过50个例子，n==0结束输入

Sample Input

7 15 16 101 0

output

最少个不同数字的n的倍数的x，若不同数字个数一样，输出最小的x

Sample Output

7 555 16 1111

根据数论里面的知识点：

对于任意的整数 n ，必然存在一个由不多于两个的数来组成的一个倍数。因为 a ，aa ， aaa…… 取 n+1 个，则由鸽笼原理，必有两个模 n 余数相同，相减即得 n 的倍数 m 。而 m 只由 a 、 0 组成。

1 #include 
         
            2 #include 
          
             3 #include 
           
              4 #include 
            
               5 #include 
             
                6 #include 
              
                7 #include 
               
                 8 #include 
                
                  9 #include 
                  10 #include 
                  
                    11 #include 
                   
                     12 #include 
                    
                      13 #include 
                     
                       14 #include 
                      
                        15 #include 
                       
                         16 #define MAX 65600 17 #define LL long long 18 #define uint unsigned short 19 using namespace std; 20 int cas=1,T,n; 21 struct node1 22 { 23 int i,r; 24 }; 25 char v1[MAX][10]; 26 int bfs1() 27 { 28 int step=1,d=0; 29 queue
                        
                         q[2]; 30 memset(v1,0,sizeof(v1[0])*n); 31 for(int i=1;i<10;i++) { q[0].push((node1){i,i%n});v1[i%n][i]=1; } 32 while(!q[d].empty()) //两个队列bfs，一个队列存一步里面走的 33 { 34 while(!q[d].empty()) 35 { 36 node1 u=q[d].front();q[d].pop(); 37 if(u.r==0) 38 { 39 for(int i=0;i
                         
                          0;n--)135 {136 if(bfs1()) continue;137 bfs2();138 }139 //printf("time=%.3lf\n",(double)clock()/CLOCKS_PER_SEC);140 return 0;141 }

View Code

转载于:https://www.cnblogs.com/cdyboke/p/5066798.html

你可能感兴趣的文章