poj 1426 Find The Multiple（bfs）

题目：http://poj.org/problem?id=1426

题意：

给出一个整数n，(1 <= n <= 200)。求出任意一个它的倍数m，要求m必须只由十进制的'0'或'1'组成。

注意：

1、要求的这个数，大数肯定不能存，需要用数组存

2、这个数的最高位一定是1

3、剩下的各个位只有两种可能，要么是1，要么是0，用bfs来处理

4、停止bfs的条件是m%n==0，即可以利用上一位的余数×10%n，若等于0，则停止，否则继续。

5、最后是输出部分，利用的是同余模定理处理，把*10操作转化为%2操作，逆向输出就可以了

代码：

#include <iostream>
#include<cstdio>
using namespace std;
int mod[600000];
int main()
{
    int n;
    int i;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)
        break;
        mod[1]=1%n;
        for(i=2;mod[i-1]!=0;i++)
        {
            mod[i]=(mod[i/2]*10+i%2)%n;//i%2模仿了广搜的两个入口
        }
        i--;
        int j=0;
        while(i)
        {
            mod[j]=i%2;//把*10操作转化为%2操作，逆向求倍数的每一位数字 
            i/=2;
            j++;
        }
        while(j)
        {
            cout<<mod[--j];
        }
        cout<<endl;
    }
    return 0;
}