首页 > 代码库 > POJ 1426 Find The Multiple（DFS，BFS）
POJ 1426 Find The Multiple（DFS，BFS）
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
26190
Sample Output
10100100100100100100111111111111111111
题意：
对于一个数字n,找到n的倍数且这个数的每一位只能是0和1。
题解:
因为是special judge，所以只要输出任何一个满足条件的就可以了。因为n<=200，所以最小满足条件的答案在18位以内（long long就足够了）。
两种解法：DFS和BFS都行。
DFS：
#include<iostream>using namespace std;int n;bool flag;void dfs(long long x,int k){ if(flag) return; if(x%n==0) { flag=true; cout<<x<<endl; return ; } if(k==18)//搜索到18位的时候还没找到就返回 return ; dfs(x*10,k+1); dfs(x*10+1,k+1);}int main(){ while(cin>>n&&n) { flag=false; dfs(1,0); } return 0;}
BFS：
#include<iostream>#include<cstring>#include<queue>using namespace std;typedef long long LL;LL bfs(int n){ queue<LL> que; que.push(1);//从1开始搜索 while(que.size()) { LL cur=que.front(); que.pop(); if(cur%n==0) return cur; que.push(cur*10); que.push(cur*10+1); } return -1;}int main(){ int n; while(cin>>n,n) { cout<<bfs(n)<<endl; } return 0;}
POJ 1426 Find The Multiple（DFS，BFS）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。