POJ1426-Find The Multiple (BFS 余数)

素颜马尾好姑娘i 2022-09-20 12:50 25阅读 0赞

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

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

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

第三份代码，感觉这个思路很好：[POJ1426-Find The Multiple - ζёСяêτ - 小優YoU][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;
    }

[POJ1426-Find The Multiple - _ - _YoU]: http://blog.csdn.net/lyy289065406/article/details/6647917