Find The Multiple（bfs）

Find The Multiple

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 20000/10000K (Java/Other)

Total Submission(s) : 43 Accepted Submission(s) : 21

Special Judge

Problem Description

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

Sample Output

100100100100100100

111111111111111111

Source

PKU

题意：构造一个十进制由0和1组成的整数m，让m能够被n整除；题目中给出了m是小于等于100位的。

思路：bfs可以做出的，只是100位这个条件让我很头疼，我先用string试了试交了之后是超时，后来看了看答案用long long也给过了，所以m肯定没有100位的；

string类型代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 
 6 using namespace std;
 7 
 8 queue<string>s;
 9 int a,c;
10 string b;
11 
12 
13 int chu(string s)
14 {
15     c=0;
16     for(int i=0;i<s.length();i++){
17         c*=10;
18         c+=s[i]-'0';
19         c%=a;
20     }
21     if(c==0)
22         return 1;
23     else
24         return 0;
25 }
26 
27 
28 int bfs()
29 {
30     while(!s.empty()){
31         b=s.front();
32         s.pop();
33         if(b.length()>100)
34             continue;
35         if(chu(b+'1')==1){
36             cout<<b+'1'<<endl;
37             while(!s.empty()){
38                 s.pop();
39             }
40             return 0;
41         }
42         else{
43             s.push(b+'1');
44         }
45 
46         if(chu(b+'0')==1){
47             cout<<b+'0'<<endl;
48             while(!s.empty()){
49                 s.pop();
50             }
51             return 0;
52         }
53         else{
54             s.push(b+'0');
55         }
56     }
57     return 0;
58 }
59 
60 
61 int main()
62 {
63 //    freopen("input.txt","r",stdin);
64     while(cin>>a){
65         if(a==0)
66             break;
67         else{
68             s.push("1");
69             bfs();
70         }
71     }
72     return 0;
73 }

View Code

long long类型代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 
 6 using namespace std;
 7 
 8 queue<long long>s;
 9 int a,c;
10 long long b;
11 
12 
13 
14 int bfs()
15 {
16     while(!s.empty()){
17         b=s.front();
18         s.pop();
19         if(b%a==0){
20             cout<<b<<endl;
21             while(!s.empty()){
22                 s.pop();
23             }
24             return 0;
25         }
26         else{
27             s.push(b*10);
28             s.push(b*10+1);
29         }
30     }
31     return 0;
32 }
33 
34 
35 int main()
36 {
37 //    freopen("input.txt","r",stdin);
38     while(cin>>a){
39         if(a==0)
40             break;
41         else{
42             s.push(1);
43             bfs();
44         }
45     }
46     return 0;
47 }

View Code