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