加载中...

POJ 1426 - Find The Multiple


问题描述

给出一个整数 n (1 <= n <= 200)。

求出任意一个它的倍数 m,要求 m 必须只由十进制的 01 组成。

解题思路

首先暴力枚举肯定是不可能的 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=10k=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=100k=101k=110k=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
  5. 我们发现 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=2k=110k%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;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
  目录