Find The Multiple
| Time Limit: 1000MS | Memory Limit: 10000K | |||
| Total Submissions: 18527 | Accepted: 7490 | 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
在广搜的题中看到这一个，表示根本想不到广搜，，，，，
每一位仅仅能是0或1，那么求n的倍数。从第一位開始搜。一直找到为止。
第一位一定是1，然后存余数temp，假设下一位是1。那么(temp*10+1)%n得到新的余数。假设是0，那么(temp*10)%n得到余数。这样进行广搜。大小是2^100
剪枝的方法：对于每个求的余数，最多有200个，每个仅仅要出现过一次就好了，出现多的减掉
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
struct node{
int k , temp ;
int last ;
}p[1000000] , q ;
int flag[210] , a[120] , n ;
int bfs()
{
int low = 0 , high = 0 ;
p[high].k = 1 ;
p[high].temp = p[high].k % n ;
flag[p[high].temp] = 1 ;
p[high++].last = -1 ;
while( low < high )
{
q = p[low++] ;
if( q.temp == 0 )
return low-1 ;
if( !flag[ (q.temp*10+1)%n ] )
{
p[high].k = 1 ;
p[high].temp = (q.temp*10+1)%n;
flag[ p[high].temp ] = 1 ;
p[high++].last = low-1 ;
}
if( !flag[ (q.temp*10)%n ] )
{
p[high].k = 0 ;
p[high].temp = (q.temp*10)%n ;
flag[ p[high].temp ] = 1 ;
p[high++].last = low-1 ;
}
}
return -1 ;
}
int main()
{
int i , j ;
while(scanf("%d", &n) && n)
{
memset(flag,0,sizeof(flag));
i = 0 ;
j = bfs();
while( j != -1 )
{
a[i++] = p[j].k ;
j = p[j].last ;
}
for(j = i-1 ; j >= 0 ; j--)
printf("%d", a[j]);
printf("
");
}
return 0;
}