POJ1426 Find The Multiple(BFS)

题目链接

题意:输入一个数a,找出一个十进制数b,b由“0”和“1”组成并且b能整除a。

思路:BFS即可,方向只有两个,样例吓唬人,6时1110就可以,其实所有数据在long long范围内就能过。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
long long b;
long long bfs(){
    queue<long long> q;
    q.push(1);
    while(1){       //while(!q.empty()){ 就WA
        long long a = q.front();
        q.pop();
        if(a%b == 0)    return a;
        q.push(a*10);
        q.push(a*10+1);
    }
}
int main(){
    //freopen("a.txt", "r", stdin);
    while(cin >> b && b){
        cout << bfs() << endl;
    }
    return 0;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with BFS