首页 > 代码库 > POJ 1426 Find The Multiple
POJ 1426 Find The Multiple
Find The Multiple
Time Limit: 1000ms
Memory Limit: 10000KB
This problem will be judged on PKU. Original ID: 142664-bit integer IO format: %lld Java class name: Main
Special Judge
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
Source
Dhaka 2002
解题：搜索。题意就是输入一个数，找出它的一个倍数，该值只包含0和1
DFS
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 int n,limit = 20;18 unsigned LL ans;19 bool dfs(unsigned LL cur,int step) {20 if(step == limit) return false;21 if(cur%n == 0) {22 ans = cur;23 return true;24 }25 if(dfs(cur*10,step+1)) return true;26 if(dfs(cur*10+1,step+1)) return true;27 return false;28 }29 int main() {30 while(scanf("%d",&n),n) {31 if(dfs(1,0)) printf("%I64u\n",ans);32 }33 return 0;34 }
BFS 貌似要快那么点点
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 int n,head,tail;18 unsigned LL q[1000000];19 unsigned LL bfs() {20 head = tail = 0;21 q[tail++] = 1;22 while(head < tail) {23 unsigned LL now = q[head++];24 if(now%n == 0) return now;25 unsigned LL tmp = now*10;26 if(tmp%n == 0) return tmp;27 q[tail++] = tmp;28 tmp = now*10+1;29 if(tmp%n == 0) return tmp;30 q[tail++] = tmp;31 }32 }33 int main() {34 while(scanf("%d",&n),n) printf("%I64u\n",bfs());35 return 0;36 }
POJ 1426 Find The Multiple
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。