欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Find The Multiple

程序员文章站 2022-05-24 09:37:54
...

【题目大意】

给定正整数n,编写程序找出非零值n的倍数m,并且m的十进制数表示仅包含数字0和1。你可以假设n不大于200,且有不超过100位的相应m。

 

【分析】

不要逐个测试n的倍数是否全由0和1组成即可,这样做会花费大量时间,效率低。

可以反过来想,只由0和1组成的数相比于整个搜索空间而言是非常少的,可以去搜索由0和1组成的数,然后通过判断这些数能否整除n来求解这个问题。于是,可将由0和1组成的数字num作为一个搜索状态。能由num扩展得到的状态有两个,一个是10*num,另一个是10*mun+1。这两个状态都必然是由0和1组成的。而且整个过程无需设置记录访问的数组。

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
void BFS(int n)
{
    queue<long long> myqueue;
    myqueue.push(1);//压入初始状态
    while(!myqueue.empty())
    {
        long long current=myqueue.front();
        myqueue.pop();
        if(current%n==0)//查找成功
        {
            cout<<current;
            return ;
        }
        myqueue.push(current*10);
        myqueue.push(current*10+1);
    }
}
int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0)
            break;
        BFS(n);
    }
    return 0;
}