POJ.1426 Find The Multiple （BFS）

题意分析

给出一个数字n，求出一个由01组成的十进制数，并且是n的倍数。

思路就是从1开始，枚举下一位，因为下一位只能是0或1，故这个数字只能是1 * 10或者1 * 10 + 1。就按照这种方式枚举，依次放入队列，如果是其的倍数，就输出。

一开始没理解题意，以为是找一个能整除的二进制数，错了半天。

代码总览

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

queue<long long> q;

long long n,ans;

void bfs()

{

    while(!q.empty()) q.pop();

    q.push(1);

    long long temp = 0;

    while(!q.empty()){

        temp = q.front();q.pop();

        if(temp%n == 0){

            ans = temp;

            return;

        }

        q.push(temp*10);

        q.push(temp*10+1);

    }

}

int main()

{

    while(scanf("%I64d",&n) != EOF && n!=0){

        bfs();

        printf("%I64d\n",ans);

    }

    return 0;

}