Find The Multiple (POJ - 1426)

题面

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.

输入

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.

输出

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.

样例输入

12
26
319
40

样例输出

110
2100100100100100100
3111111111111111111

提示

无

思路

一维bfs

代码

 1using namespace std;
 2typedef long long ll;
 3const int inf = 0x3f3f3f3f;
 4const int N = 15+5;
 5
 6int n;
 7
 8void bfs() {
 9    queue<ll> q;
10    q.push(1);
11    while(!q.empty()) {
12        ll t = q.front();
13        q.pop();
14        if(t%n==0) {
15            printf("%lld\n", t);
16            return ;
17        }
18        q.push(t*10);
19        q.push(t*10+1);
20    }
21}
22
23int main(void) {
24
25    while(scanf("%d", &n)==1 && n) {
26        bfs();
27    }
28    return 0;
29}