POJ1426-Find The Multiple (BFS 余数)-蒲公英云

POJ1426-Find The Multiple (BFS 余数)

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

第一份代码，记录路径的BFS

第二份代码，忘记是从哪里看的了……

第三份代码，感觉这个思路很好：POJ1426-Find The Multiple - ζёСяêτ - 小優YoU

#include <cstdio>
#include <cstring>
const int N=1000005;
int n;
int que[N],pre[N],q[N],ans[205];//que[] 0、1，q[]当前余数，pre[]前驱。
int bfs ()
{
    int head=0,tail=1,now,next,i;
    que[1]=1;pre[1]=0;q[1]=1;
    while (head<tail)
    {
        now=q[++head]*10;
        for (i=0;i<=1;i++)
        {
            next=now+i;
            tail++;
            que[tail]=i;
            q[tail]=next%n;
            pre[tail]=head;
            if (q[tail]==0)
                return tail;
        }
    }
}
int main ()
{
    while (scanf("%d",&n),n)
    {
        int cnt=0,i=bfs();
        while (i)
        {
            ans[++cnt]=que[i];
            i=pre[i];
        }
        for (i=cnt;i>=1 ;i-- )
            printf("%d",ans[i]);
        printf("\n");
    }
    return 0;
}
#include <cstdio>
#include <cstring>
int n;
__int64 now,q[1000000];
void bfs ()
{
    int head=0,tail=1,i;
    q[tail]=1;
    while (head<tail)
    {
        head++;
        now=q[head];
        now*=10;
        if (now%n==0)
            break;
        for (i=0;i<=1;i++)
        {
            tail++;
            q[tail]=now+=i;
        }
    }
    printf("%I64d\n",now);
}
int main ()
{
    while (scanf("%d",&n),n)
        bfs();
    return 0;
}
//http://blog.csdn.net/lyy289065406/article/details/6647917
#include <cstdio>
#include <cstring>
int mod[600000];
int main ()
{
    int n,i;
    while (scanf("%d",&n),n)
    {
        mod[1]=1;  //初始化，n倍数的最高位必是1
        for (i=2;mod[i-1]!=0;i++)  //利用同余模定理，从前一步的余数mod[i/2]得到下一步的余数mod[i]
            mod[i]=(mod[i/2]*10+i%2)%n;
                     //mod[i/2]*10+i%2模拟了BFS的双入口搜索
                     //当i为偶数时，+0，即取当前位数字为0  。为奇数时，则+1,即取当前位数字为1
        i--;
        int pm=0;
        while (i)
        {
            mod[pm++]=i%2;   //把*10操作转化为%2操作，逆向求倍数的每一位数字
            i/=2;
        }
        while (pm)
            printf("%d",mod[--pm]);
        printf("\n");
    }
    return 0;
}