2.8　找符合条件的整数

任意给定一个正整数N，求一个最小的正整数M（M ＞1），使得N*M的十进制表示形式里只含有1和0。

最初的解法

看了题目要求之后，我们的第一想法就是从小到大枚举M的取值，然后再计算N*M，最后判断它们的乘积是否只含有1和0。大体的思路可以用下面的伪代码来实现：

但是问题很快就出现了，什么时候应该终止循环呢？这个循环会终止吗？即使能够终止，也许这个循环仍需要耗费太多的时间，比如N＝99时，M＝1122334455667789，N*M＝111111111111111111。

分析与解法

题目中的直接做法显然不是一个令人满意的方法。还有没有其他的方法呢？答案是肯定的。

可以做一个问题的转化。由于问题中要求NM的十进制表示形式里只含有1和0，所以NM与M相比有明显的特征。我们不妨尝试去搜索它们的乘积NM，这样在某些情况下需要搜索的空间要小很多。另外，搜索NM，而不去搜索M，其实有一个更加重要的原因，就是当M很大时，特别是当M大于2³²时，某些机器就可能没法表示M了，我们就得自己实现高精度大整数类。但是考虑NM的特点，可以只需要存储NM的十进制表示中“1”的位置，这样就可以大大缩小为表示NM所需要的空间，从而使程序能处理数值很大的情况。因此，考虑到程序的推广性，选择了以NM为目标进行计算。

换句话说，就是把问题从“求一个最小的正整数M，使得N*M的十进制表示形式里只含有1和0”变成求一个最小的正整数X，使得X的十进制表示形式里只含有1和0，并且X被N整除。

我们先来看一下X的取值，X从小到大有如下的取值：1、10、11、100、101、110、111、1000、1001、1010、1011、1100、1101、1110、1111、10000、……

如果直接对X进行循环，就是先检查X＝1是否可以整除N，再检查X＝10，然后检查X＝11，接着检查X＝100…（就像遍历二进制整数一样遍历X的各个取值）。但是这样处理还是比较慢，如果X的最终结果有K位，则要循环搜索2^K次。由于我们的目标是寻找最小的X，使得X mod N＝0，我们只要记录mod N＝i（0＜＝i＜N）的最小X就可以了。这样通过避免一些不必要的循环，可以达到加速算法的目的。那么如何避免不必要的循环呢？先来看一个例子：

设N＝3，X＝1，再引入一个变量j，j＝X％N。直接遍历X，计算中间结果如表2-1所示：

表2-1

表2-1计算110％3是多余的。原因是1和10对3的余数相同，所以101和110对3的余数相同，那么只需要判断101是否可以整除3就可以了，而不用判断110是否能整除3。并且，如果X的最低3位是110，那么可以通过将101替换110得到一个符合条件的更小正整数。因此，对于mod N同余的数，只需要记录最小的一个。

有些读者可能会问，当X循环到110时，我怎么知道1和10对3的余数相同呢？其实，X＝1，X＝10是否能整除3，在X循环到110时都已经计算过了，只要在计算X＝1，X＝10时，保留X％N的结果，就可以在X＝110时作出判断，从而避免计算X％N。

以上的例子阐明了在计算中保留X除以N的余数信息可以避免不必要的计算。下面给出更加形式化的论述。

假设已经遍历了X的十进制表示有K位时的所有情况，而且也搜索了X＝10^K的情况，设10^K％N＝a。现在要搜索X有K＋1位的情况，即X＝10^K＋Y，（0＜Y＜10^K）。如果用最简单的方法，搜索空间（Y的取值）将有2^K－1个数据。但是如果对这个空间进行一下分解，即把Y按照其对N的余数分类，我们的搜索空间将被分成N－1个子空间。对于每个子空间，其实只需要判断其中最小的元素加上10^K是否能被N整除即可，而没有必要判断这个子空间里所有元素加上10^K是否能被N整除。这样搜索的空间就从2^K－1维压缩到了N－1维。但是这种压缩有一个前提，就是在前面的计算中已经保留了余数信息，并且把Y的搜索空间进行了分解。所谓分解，其实，从技术上讲，就是对于“X模N”的各种可能结果，保留一个对应的已经出现了的最小的X（即建立一个长度为N的“余数信息数组”，这个数组的第i位保留已经出现的最小的模N为i的X）。

那么现在的问题就是如何维护这个“余数信息数组”了。假设已经有了X的十进制表示有K位时的所有余数信息。也有了X=10^K的余数信息。现在我们要搜索X有K＋1位的情况，也即X=10^K＋Y，（0＜Y＜10^K）时，X除以N的余数情况。由于已经有了对Y的按除N的余数进行的空间分解情况，即Y＜10^K的余数信息数组。我们只需要将10^K％N的结果与余数信息数组里非空的元素相加，再去模N，看看会不会出现新的余数即可。如果出现，就在余数信息数组的相应位置增添对应的X。这一步只需要N次循环。

综上所述，假设最终的结果X有K位，那么直接遍历X，需要循环2^K次，而按照我们保留余数信息避免不必要的循环的方法，最多只需要（K－1）*N步。可以看出，当最终结果比较大时，保留余数信息的算法具有明显的优势。

下面是这个算法的伪代码：BigInt[i]表示模N等于i的十进制表示形式里只含1和0的最小整数。由于BigInt[i]可能很大，又因为它只有0和1，所以，只需要记下1的位置即可。比如，整数1001，记为（0，3）＝10⁰＋10³。即BigInt的每个元素是一个变长数组，对于模N等于i的最小X，BigInt的每个元素将存储最小X在十进制中表示“1”的位置。我们的目标就是求BigInt[0]。

代码清单2-17

在上面的实现中，循环节取值N（其实循环节小于等于N，循环节就是最小的c，使得10^cmod N＝1）。

这个算法其实部分借鉴了动态规划算法的思想。在动态规划算法的经典实例“最短路径问题”中，当处理中间结点时，只需要得到从起点到中间结点的最短路径，而不需要中间结点到那个端点的所有路径信息。“只保留模N的结果相同的X中最小的一个”的方法，与此思路相似。

扩展问题

1．对于任意的N，一定存在M，使得N*M的乘积的十进制表示只有0和1吗？

2．怎样找出满足题目要求的N和M，使得N*M＜2¹⁶，且N＋M最大？