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
26190
Sample Output
10100100100100100100111111111111111111
在广搜的题中看到这一个，表示根本想不到广搜，，，，，
每一位仅仅能是0或1，那么求n的倍数。从第一位開始搜。一直找到为止。
第一位一定是1，然后存余数temp，假设下一位是1。那么(temp*10+1)%n得到新的余数。假设是0，那么(temp*10)%n得到余数。这样进行广搜。大小是2^100
剪枝的方法：对于每个求的余数，最多有200个，每个仅仅要出现过一次就好了，出现多的减掉
#include#include #include 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("\n"); } return 0;}