题目描述

Description

Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.
Input

The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.
Output

For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.

样例

Sample Input

2
6
19
0
Sample Output

10
100100100100100100
111111111111111111

算法

(宽度优先搜索+枚举)

本题乍看之下好像和宽度优先搜索无关，只需逐个测试n的倍数是否全由0和1组成 即可，但这样做相当于枚举，需要枚举〃在整个搜索空间(小于100位的整数)中的所 有倍数，这个计算量非常大，因为逐个判断会花费大量时间，因此这种方法的效率非常低。
可以反过来想这个问题：只由。和1组成的数相比于整个搜索空间而言是非常少的， 可以去搜索由0和1组成的数，然后通过判断这些数能否整除n来求解这个问题。
于是，可将由0和1组成的数字num作为一个搜索状态。能由num扩展得到的状态有 两个，一个是10num,另一个是10num+1o这两个状态必然都是由0和1组成的。若将 num的初始状态设置为1,则可通过状态的扩展来覆盖整个查找空间中由。和1组成的数。
由于从初始状态1开始不断扩展，扩展的数字必定比之前的数字大，扩展出来的状态 不可能在此前出现过，因此不需要用数组来记录访问过的数字。

C++ 代码

#include<iostream> 
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
void bfs(int n){
    queue<ll> q;
    q.push(1);
    while(!q.empty()&&q.size()<=100){
        ll current=q.front();
        q.pop();
        if(current%n==0){
            cout<<current<<endl;
            return ;
        }
        q.push(current*10);
        q.push(current*10+1);
    }
}
int main(){
      int n;
      while(cin>>n){
        if(n==0){
            break;
          }
          bfs(n); 
      }
    return 0;
}