简单搜索–DFS–Find The Multiple
Description
给定一个正整数n,编写一个程序来找出一个n的非零倍数m,它的十进制表示法仅包含数字0和1。你可以假设n不大于200,并且对应的m不包含100小数位数。
Input
输入文件可能包含多个测试用例。每一行包含一个值n(1<=n<=200)。包含零的行结束输入。
Output
对于输入中的n个值,打印一行,其中包含m的对应值。m的十进制表示不能包含超过100位数字。如果给定值n有多个解,则其中任何一个都是可接受的。
Sample Input
2
6
19
0
Sample Output
10
100100100100100100
111111111111111111
用DFS遍历,每次有两种情况x10或者x10+1
考虑这道题的范围,要用longlong
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <string>
#include <stack>
#include <queue>
#include <map>
using namespace std;
const int inf=0x3f3f3f3f;
long long n,anw;
void dfs(long long q,int step)
{
if(anw) return ;
if(q%n==0)
{
anw=q;
return ;
}
if(step==18) return ;
dfs(q*10,step+1);
dfs(q*10+1,step+1);
}
int main()
{
while(true)
{
cin>>n;
if(n<1||n>200) break;
anw=0;
dfs(1,0);
cout<<anw<<endl;
}
return 0;
}
Wardell Ⅱ
发布了7 篇原创文章 · 获赞 0 · 访问量 70
私信
关注