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

struct node

{

    int val;

    int pre;

};

int n;

int ans[MAXN];

node D[MAXN];

void solved()

{

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

    queue<int> Q;

    Q.push();

    D[].val = ;

    D[].pre = -;

    while ( !Q.empty() )

    {

        int cur = Q.front();

        Q.pop();

        if ( cur ==  )

            break;

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

        bool find = false;

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

        {

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

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

            {

                D[tp].val = i;

                D[tp].pre = cur;

                Q.push( tp );

            }

            if ( tp ==  )

            {

                find = true;

                break;

            }

        }

        if ( find ) break;

    }

    return;

}

bool GetStart()

{

    char str[];

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

    int len = strlen(str);

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

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

        return false;

    return true;

}

int main()

{

    int T;

    scanf( "%d", &T );

    while ( T-- )

    {

        scanf( "%d", &n );

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

        else

        {

            solved();

            int cnt = ;

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

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

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

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

            puts("");

        }

    }

    return ;

}