Find the Multiple POJ1426

题目链接：Find the Multiple

题目大意

找出一个只由0和1组成的能整除n的数。

思路

所有由0和1组成的数可以看作是某个只由0、1组成的数a经过以下两种变化得到

　　1、a * 10

　　2、a * 10+1

因此只需要用BFS搜索满足条件的数即可。

题解

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

long long n;
int main(int argc, char const *argv[])
{
    while(cin >> n && n)
    {
        queue<long long> q;
        q.push(1);
        while(!q.empty())
        {
            if(q.front() % n == 0)
            {
                cout << q.front() << endl;
                break;
            }
            q.push(q.front()*10);
            q.push(q.front()*10+1);
            q.pop();
        }
    }
    return 0;
}