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
我们分析一下就是建立K*10+1和k*10中必定是由0和1组成的，这样我们按照这个模板套。
具体操作看代码
dfs的ac代码；
#include <iostream> #include <cstdio> #include <cstring> using namespace std; long n; int a[200]; int flag; void dfs(int c,long long k){ if(flag||c>=19)return;//控制位数的作用，不要无限搜 if(k%n==0){//出现就退出循环 printf("%lld\n",k); flag=1; return; } dfs(c+1,k*10);//偶数 dfs(c+1,k*10+1);//奇数 } int main() { while(scanf("%ld",&n)!=EOF){ if(n==0) break; flag=0; dfs(0,1); } }
bfs的ac代码
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> using namespace std; int n; struct ss { long long a; }; ss f[10000005],res; void bfs() { int l=0,r=1; f[1].a=1; while (l<r) { l++; if (f[l].a%n==0) { cout<<f[l].a<<endl; return; } r++; f[r].a=f[l].a*10+1; r++; f[r].a=f[l].a*10; } } int main() { while (scanf("%d",&n)!=EOF) { if (!n) break; bfs(); } return 0; }
