题意：给一些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 ;
}