王道机试指南 例题9.2 Find The Multiple

题目：

题目大意：

算法与分析：

宽度优先算法。

代码：

#include <queue>
#include <iostream>
#include <cstdio>
using namespace std;

long long BFS(int n){
    queue<long long> q;
    q.push(1);
    while(q.empty()==0){
        long long tmp=q.front();
        if(tmp%n==0) return tmp;
        q.pop();
        q.push(tmp*10);
        q.push(tmp*10+1);
    }
    return -1;
}

int main(){
    int n;
    while(cin>>n && n!=0){
        printf("%lld\n",BFS(n));
    }
    return 0;
}

运行结果：