POJ1426–Find The Multiple
目录
一、题目链接
二、题目内容
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.
Input
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.
Output
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.
Sample Input
2
6
19
0
Sample Output
10
100100100100100100
111111111111111111
翻译
给定一个正整数n，编写一个程序以找出n的非零倍数m，其十进制表示形式仅包含数字0和1。您可以假定n不大于200，并且对应的m包含不超过100十进制数字。
三、题意拆解
- 题意乍一看有点绕，什么n的m倍云云。所以我们依旧老样子拆题。
- 首先，题目会给我们一个数n，我们的目标是找到一个数m，这个m是n的非零倍数。比如n=2，那我们找的m就必须是2的倍数，如4，6，8……
- 其次，m的十进制表达形式只能含有0和1
- 最后，n不大于200，m的位数不超过100.
- 最最后，m有很多结果，任一个结果输出都算正确。
四、解题思路
- 这题第一眼过去就是很简单的一个搜索题，找出n的倍数里面只包含0和1的数。但如果这么简单就能写出结果
那我也没法拿这题水博客，那么这博客也就没有它的意义了。 - 首先，我们看到m只能包含0和1，这种形式第一眼就能令人联想到二进制表达形式。所以我们可以遍历所有符合二进制表示的十进制数，找到第一个n的倍数，它就是我们要找的m。
- 二进制的表达形式，每一位数字都有两种选择，0或者1，譬如
首位为1，那么它的衍生数就是
10|11
10也有两个衍生数，分别是100，111
以此类推，由此可见，每一个二进制表达式都能衍生出两个子数，我们画个图出来，就是这个样子的
很明显，这是一个树状结构，而且还是一个二叉树。那么，我们就可以用对二叉树的操作来完成这道题。
- 那么就很简单了，直接对二进制数进行bfs，找到n的倍数输出就行了。需要注意的就是数值比较大，定义数值类型要用 long long类型。
这一题思路其实蛮简单的，主要是如何想到bfs这条路。
五、参考代码
//
// Created by Verber on 2021/1/23.
//
#include<cstdio>
#include<algorithm>
#include<iostream>
#include "string.h"
#include "set"
#include "queue"
typedef long long ll ;
using namespace std;
void bfs(int n)//对二进制数进行判断
{
queue<ll>q;//数值类型为long long类型
q.push(1);
while (!q.empty())
{
ll ls = q.front();
if(ls%n!=0)//不是n的倍数将两个子数入队
{
q.push(ls*10);
q.push(ls*10+1);
} else
{
cout<<ls<<endl;
return;
}
q.pop();
}
}
int main()
{
ll n;
while (cin>>n)
{
if(n==0)break;
bfs(n);
}
}