- POJ 1426 - Find The Multiple
- Time: 1000MS
- Memory: 10000K
- 难度: 初级
- 分类: BFS
问题描述
给出一个整数n (1 <= n <= 200
)。
求出任意一个它的倍数m,要求m必须只由十进制的 0
或 1
组成。
解题思路
首先暴力枚举肯定是不可能的 1000ms 想不超时都难,而且枚举还要解决大数问题。
解题方法: BFS+同余模定理
首先说说朴素的不剪枝搜索方法:
我以 n=6
为例
首先十进制数,开头第一个数字(最高位)一定不能为0,即最高位必为 1
设6的 “01十进制倍数” 为k,那么必有 k%6 = 0
,现在就是要用BFS求k值:
1、先搜索k的最高位,最高位必为1,则此时 k=1
,但 1%6 = 1 != 0
因此 k=1
不是所求,存储余数 1
2、搜索下一位,此时有两种可能:
下一位可能为 0,即 k*10+0
,此时 k=10
,那么 k%6=4
可能为 1,即 k*10+1
,此时 k=11
,那么 k%6=5
由于余数均不为0,即 k=10
与 k=11
均不是所求
3、继续搜索第三位,此时有四种可能了:
对于 k=10
,
下一位可能为0,即 k*10+0
,此时 k=100
,那么 k%6=4
下一位可能为1,即 k*10+1
,此时 k=101
,那么 k%6=5
对于k=11,
下一位可能为0,即 k*10+0
,此时 k=110
,那么 k%6=2
下一位可能为1,即 k*10+1
,此时 k=111
,那么 k%6=3
由于余数均不为0,即 k=100
,k=101
,k=110
,k=111
均不是所求
4、继续搜索第四位,此时有八种可能了:
对于k=100,
下一位可能为0,即 k*10+0
,此时 k=1000
,那么 k%6=4
下一位可能为1,即 k*10+1
,此时 k=1001
,那么 k%6=5
对于k=101,
下一位可能为0,即 k*10+0
,此时 k=1010
,那么 k%6=2
下一位可能为1,即 k*10+1
,此时 k=1011
,那么 k%6=3
对于k=110,
下一位可能为0,即 k*10+0
,此时 k=1100
,那么 k%6=2
下一位可能为1,即 k*10+1
,此时 k=1101
,那么 k%6=3
对于k=111,
下一位可能为0,即 k*10+0
,此时 k=1110
,那么 k%6=0
下一位可能为1,即 k*10+1
,此时 k=1111
,那么 k%6=1
我们发现 k=1110
时,k%6=0
,即 1110 就是所求的倍数
从上面的演绎不难发现,用BFS是搜索 当前位数字 (除最高位固定为1),因为每一位都只有0或1两种选择,换而言之是一个双入口BFS。
本题难点在于搜索之后的处理:对余数的处理,对大数的处理,余数与所求倍数间的关系。
接下来说说处理大数问题和剪枝的方法:
首先我们简单回顾一下 朴素搜索 法:
n=6
1%6=1 (k=1)
{
(1*10+0)%6=4 (k=10)
{
(10*10+0)%6=4 (k=100)
{
(100*10+0)%6=4 (k=1000)
(100*10+1)%6=5 (k=1001)
}
(10*10+1)%6=5 (k=101)
{
(101*10+0)%6=2 (k=1010)
(101*10+1)%6=3 (k=1011)
}
}
(1*10+1)%6=5 (k=11)
{
(11*10+0)%6=2 (k=110)
{
(110*10+0)%6=2 (k=1100)
(110*10+1)%6=3 (k=1101)
}
(11\*10+1)%6=3 (k=111)
{
(111\*10+0)%6=0 (k=1110) 有解
(111\*10+1)%6=1 (k=1111) 由于前面有解,这个余数不存储
}
}
}
从上面可以看出余数的存数顺序(逐层存储):
用数组 mod[]
存储余数,其中 mod[0]
不使用,由 mod[1]
开始
那么mod中的余数依次为: 1 4 5 4 5 2 3 4 5 2 3 2 3 0
共14个
即说明我们得到 余数0 之前,做了14步 *10
的操作,那么当n值足够大的时候,是很容易出现k为大数的情况(事实上我做过统计,200以内的n,有18个n对应的k值为大数)
那么我们若再用int去存储k就显得不怎么明智了。
为了处理所有情况,我们自然会想到 是不是应该要用 int[]
去存储k的每一位?
而又由于k是一个01序列,那能不能把 *10
得到k每一位的问题 转化为模2的操作得到k的每一位(0或1) 呢?
答案是可以的。
首先我们利用 同余模定理 对得到余数的方式进行一个优化:
(a*b)%n = (a%n * b%n)%n
(a+b)%n = (a%n + b%n)%n
随便抽取上面一条式子为例
- 前一步
(11*10+0)%6=2
即k=110
,k%6=2
- 当前步
(110*10+0)%6=2
由同余模定理 (110*10+0)%6 = ((110*10)%6+0%6)%6 = ((110%6 * 10%6)%6 + 0)%6 = (11*10+0)%6 = 2
所以当前步 (110*10+0)%6
可以转变为 (2*10+0)%6=2
很显然地,这种处理把 k=110
等价于 k=2
即用 前一步操作得到的余数 代替 当前步的k值
而n在200的范围内, 余数值不可能超过3位数, 这就解决了 大数的问题
通过这种处理手法,我们只需在BFS时顺手存储一个 余数数组 mod[]
,就能通过 mod[i-1]
得到 mod[i]
,直到 mod[i]==0
时结束,大大减少了运算时间
前面已经提到,n=6时,求余操作进行了14次,对应地,BFS时 *10
的操作也进行了14次。
令 i=14
,通过观察发现,i%2
恰好就是 6 的倍数的最低位数字
i/2
再令 i%2
,恰好就是 6 的倍数的 次低位数字。。。
循环这个操作,直到 i=0
,就能得到 6的 01倍数(一个01队列),倒序输出就是所求
这样就完成了 *10
操作到 %2
操作的过渡。
由于n值有限,只是1到200的整数,因此本题也可以用打表做,通过上面的方法得到结果后,就把 1 ~ 200 的倍数打印出来,重新建立一个程序,直接打表就可以了。
不过打表比上面介绍的方法快不了多少。
AC 源码
//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;
}