DFS/BFS(同余模) POJ 1426 Find The Multiple-白红宇

DFS/BFS(同余模) POJ 1426 Find The Multiple

阅读量：6402 次

发布时间：2019-06-23

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

1 /* 2     题意：找出一个0和1组成的数字能整除n 3     DFS：200的范围内不会爆long long，DFS水过~ 4 */ 5 /************************************************ 6 Author        :Running_Time 7 Created Time  :2015-8-2 14:21:51 8 File Name     :POJ_1426.cpp 9 *************************************************/10 11 #include 
     
      12 #include 
      
       13 #include 
       
        14 #include 
        
         15 #include 
         
          16 #include 
          
           17 #include 
           
            18 #include 
            
             19 #include 
             
              20 #include 
              
               21 #include 
               
                22 #include 
                
                 23 #include 
                 24 #include 
                  
                   25 #include 
                   
                    26 #include 
                    
                     27 #include 
                     
                      28 using namespace std;29 30 typedef long long ll;31 const int MAXN = 1e4 + 10;32 const int INF = 0x3f3f3f3f;33 const int MOD = 1e9 + 7;34 ll n;35 bool ok;36 37 void DFS(ll x, int step, int dep) {38 if (ok) return ;39 if (step >= dep) return ;40 if (x % n == 0) {41 printf ("%I64d\n", x);42 ok = true; return ;43 }44 DFS (x * 10, step + 1, dep);45 DFS (x * 10 + 1, step + 1, dep);46 }47 48 int main(void) { //POJ 1426 Find The Multiple49 while (scanf ("%I64d", &n) == 1) {50 if (!n) break;51 ok = false; ll dep = 1;52 while (true) {53 if (ok) break;54 DFS (1, 0, dep); dep++;55 }56 }57 58 return 0;59 }

1 /* 2     BFS+同余模定理：mod数组保存，每一位的余数，当前的数字由少一位的数字递推， 3         比如4(100)可以从2(10)递推出，网上的代码太吊，膜拜之 4     详细解释：http://blog.csdn.net/lyy289065406/article/details/6647917 5 */ 6 /************************************************ 7 Author        :Running_Time 8 Created Time  :2015-8-2 15:14:33 9 File Name     :POJ_1426_BFS.cpp10 *************************************************/11 12 #include 
      
       13 #include 
       
        14 #include 
        
         15 #include 
         
          16 #include 
          
           17 #include 
           
            18 #include 
            
             19 #include 
             
              20 #include 
              
               21 #include 
               
                22 #include 
                
                 23 #include 
                 
                  24 #include 
                  25 #include 
                   
                    26 #include 
                    
                     27 #include 
                     
                      28 #include 
                      
                       29 using namespace std;30 31 #define lson l, mid, rt << 132 #define rson mid + 1, r, rt << 1 | 133 typedef long long ll;34 const int MAXN = 1e6 + 10;35 const int INF = 0x3f3f3f3f;36 const int MOD = 1e9 + 7;37 int mod[MAXN];38 int ans[MAXN];39 40 int main(void) {41 int n;42 while (scanf ("%d", &n) == 1) {43 if (!n) break;44 mod[1] = 1; int i;45 for (i=2; mod[i-1]; ++i) {46 mod[i] = (mod[i/2] * 10 + (i&1)) % n; //BFS双入口模拟47 }48 int t = 0; i--;49 while (i) {50 ans[++t] = i & 1;51 i /= 2;52 }53 while (t) {54 printf ("%d", ans[t--]);55 }56 puts ("");57 }58 59 return 0;60 }