Find The Multiple
| Time Limit: 1000MS |
? |
Memory Limit: 10000K |
| Total Submissions: 20235 |
? |
Accepted: 8203 |
? |
Special Judge |
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
2
6
19
0
Sample Output
10
100100100100100100
111111111111111111
题目大意：给一个数n，求最小的k，使得k是n的整数倍，且k的十进制表示只有0和1.
题目上说这样的k不会超过200位，确实是真的，不过这样太吓人了，其实在1~200里的全部n的结果k都是在64位之内的，它特意说不超过200位，一开始把我吓坏了，这题用广搜怎么可能做呢，太坑爹了这题。
广搜，其实这个全部数据里最大的也不过是n=198时，k=1111111111111111110（不用数了，一共18个1，1个0）
AC代码：
#include
#include
using namespace std; typedef __int64 ll; void bfs(int n){ queue
que; que.push(1); while(!que.empty()){ ll t=que.front(); que.pop(); if(t%n==0){ printf("%I64d\n",t); return ; } que.push(t*10); que.push(t*10+1); } } int main() { int i,n; while(scanf("%d",&n),n) bfs(n); return 0; }
下面还有一个代码，写的基本上一致，只不过把bfs改成了__int64的带返回值，然后在main输出结果，W!A!了。。。。我不明白，路过的大神帮忙指点一下可好
#include
#include
using namespace std; typedef __int64 ll; ll bfs(int n){ queue
que; que.push(1); while(!que.empty()){ ll t=que.front(); que.pop(); if(t%n==0) return t; que.push(t*10); que.push(t*10+1); } } int main() { int i,n; while(scanf("%d",&n),n) printf("%I64d\n",bfs(n)); return 0; }