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的倍数且这个数的每一位只能是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; }