Description

Input

Output

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("\n");

    }

    return 0;

}