POJ 1426 Find The Multiple (廣搜)

POJ 1426 Find The Multiple (廣搜)

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;
}