POJ 1426 Find The Multiple（不断学习！）

【题意简述】：输入一个数，找出它的一个倍数，这个倍数只能用0和1表示。

【思路】：一开始想到的是用简单的朴素的BFS，用队列帮助实现，可是超时！这个是超时代码：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

__int64 bfs(int m)
{
	queue<__int64> q;
	__int64 temp;
	q.push(1);
	while(!q.empty())
	{
		temp = q.front();
		q.pop();
		if(temp%m == 0)
			return temp;
		q.push(temp*10+1);
		q.push(temp*10);
	}
	return 0;
}

int main()
{
	int n;
	while(cin>>n&&n)
	{
		cout<<bfs(n)<<endl;
	}
	return 0;
}

//Memory Time
//2236K  32MS 

#include<iostream>
using namespace std;

int mod[524286];  //保存每次mod n的余数
                  //由于198的余数序列是最长的
                  //经过反复二分验证，436905是能存储198余数序列的最少空间
                  //但POJ肯定又越界测试了...524286是AC的最低下限，不然铁定RE

int main(int i)
{
	int n;
	while(cin>>n)
	{
		if(!n)
			break;

		mod[1]=1%n;  //初始化，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)
			cout<<mod[--pm];  //倒序输出
		cout<<endl;
	}
	return 0;
}

这个代码也是可以AC的：From： http://www.cnblogs.com/crazyapple/archive/2013/06/03/3116169.html

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
 
 __int64 mod[600000];
 
int main()
{
     int n;
     while(~scanf("%d",&n)&&n)
     {
         int i;
         for(i=1;;i++)
         {
             mod[i]=mod[i/2]*10+i%2;
             if(mod[i]%n==0)
             {
                 break;
             }
         }
         printf("%I64d\n",mod[i]);
     }
     return 0;
}

POJ 1426 Find The Multiple（不断学习！）,布布扣,bubuko.com

POJ 1426 Find The Multiple（不断学习！）

原文：http://blog.csdn.net/u013749862/article/details/23021001