SPOJ 370 Ones and zeros BFS + 동 여 가지치기

제목: n 을 주 고 0, 1 만 포함 하 는 n 의 배 수 를 구하 세 요.
두 수 a, b 만족: a < b 및 a% n = b% n.
만약 (a * 10 ^ x + c)% n = z 라면 동 여 정리 에 따라 (b * 10 ^ x + c)% n 도 z 와 같다.
b 의 상황 은 사실 a 와 같 습 니 다. 만약 에 a 가 조건 에 부합 되 지 않 으 면 b 는 반드시 조건 에 부합 되 지 않 습 니 다.
따라서 우 리 는 검색 할 때 1 부터 매번 0 이나 1 을 뒤로 추가 하고 얻 은 숫자 가 이전에 얻 은 숫자 와 같 으 면 버 리 고 그렇지 않 으 면 대열 에 넣 어 계속 검색 합 니 다.
 

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>



using namespace std;



const int MAXN = 20010;



struct node

{

    int val;

    int pre;

};



int n;

int ans[MAXN];

node D[MAXN];



void solved()

{

    memset( D, -1, sizeof(D) );

    queue<int> Q;

    Q.push(1);

    D[1].val = 1;

    D[1].pre = -1;



    while ( !Q.empty() )

    {

        int cur = Q.front();

        Q.pop();

        if ( cur == 0 )

            break;

        //printf( "%d
", cur );



        bool find = false;

        for ( int i = 0; i < 2; ++i )

        {

            int tp = ( cur * 10 + i ) % n;

            if ( D[tp].val == -1 )

            {

                D[tp].val = i;

                D[tp].pre = cur;

                Q.push( tp );

            }

            if ( tp == 0 )

            {

                find = true;

                break;

            }

        }

        if ( find ) break;

    }

    return;

}



bool GetStart()

{

    char str[10];

    sprintf( str, "%d", n );

    int len = strlen(str);

    for ( int i = 0; i < len; ++i )

    if ( str[i] != '0' && str[i] != '1' )

        return false;

    return true;

}



int main()

{

    int T;

    scanf( "%d", &T );

    while ( T-- )

    {

        scanf( "%d", &n );

        if ( GetStart() ) printf( "%d
", n );

        else

        {

            solved();

            int cnt = 0;

            for ( int i = 0; i != -1; i = D[i].pre )

                ans[cnt++] = D[i].val;

            for ( int i = cnt - 1; i >= 0; --i )

                printf( "%d", ans[i] );

            puts("");

        }

    }

    return 0;

}