POJ-1426 0|1からなる10進数整除問題

///  :    n,       ans    ans        0   1；
///                       ，    dfs bfs   ；
///bfs c++ TLE， g++   4       ；                ；


///     bfs                TLE ；      ；
/*#include
#include
using namespace std;

typedef long long LL;
LL n;

void bfs()
{
    queueQ;
    Q.push(1);
    while(!Q.empty())
    {
        LL now=Q.front();
        Q.pop();
        if(now%n==0)
        {printf("%lld
",now);return;}
        Q.push(now*10);
        Q.push(now*10+1);
    }
    return ;
}

int main ()
{
    while(scanf("%lld",&n))
    {
        if(n==0) break;
        bfs();
    }
}
*/


///141ms
///           19  OK ；
#include
using namespace std;

typedef unsigned long long LL;///            long long                                ；

int  n;
bool flag;

void dfs(LL k1,LL k2)
{
    if(flag) return ;///                    dfs ；
    if(k1%n==0){ printf("%I64u
",k1);flag=true;return ;}
    if(k2==19) return ;///          19；          。
    dfs(k1*10,k2+1);
    dfs(k1*10+1,k2+1);
}
int main ()
{
    while(scanf("%d",&n)&&n)
    {
        flag=false;
        dfs(1,0);
    }
    return 0;
}