POJ 1426 - Find The Multiple
分类: 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 不是所求