POJ 1426

• 找到一个数字X(只由1,0组成),且$ X \% n == 0 $,(数字X能够被n整除)
• 输出任意的一个X
• 还是想不到要用BFS，从1开始bfs,加入数字ncur = cur * 10 + i,保证了数字都由1 0组成,

  #include <iostream>
  #include <queue>
  #include <string.h>
  
  using namespace std;
  
  bool vis[201];
  int n;
  queue<long long> que;
  
  void init() {
      memset(vis,0,sizeof vis);
      while ( !que.empty() ) que.pop(); 
  }
  
  long long bfs(int mod) {
      que.push(1);
      while ( !que.empty() ) {
          long long cur = que.front();
          que.pop();
  
          int k = cur % mod;
          if (k == 0 ) return cur;
  
          if ( !vis[k] ) {
              vis[k] = 1; // 标记 取余的数
              for (int i=0; i<=1; i++) {
                  long long ncur = cur * 10 + i;
                  if (ncur % mod == 0) return ncur;
                  que.push(ncur);
              }
          }
      }
      return 0;
  }
  
  int main() {
  
      while (cin >> n && n) {
          init();
          cout << bfs(n) << endl;
      }
      return 0;
  }