2.8找符合条件的整数

问题描述：给定一个正整数N,求一个最小正整数M(M>1)，使得N*M的十进制表示形式里只含有1和0.

 

最直接了当的方法。当然就是对M无限穷举下去。

 

书上提供了一个逆向考虑的方法。

其实重点是思想。

我们可以穷举N*M。即由1和0构成的串。

相比穷举M而言。N*M的数量级小得多了多！。

而且我们判断合法的时候只要判断构造出来的串是否整除N.即可。

 

相似的。曾经遇到过一个这样的问题。

输入数据N,M。其中0<N<M<1e9。打印出[N,M]中的回文素数。

有常识的话。可以知道1e9素数数量有500W。我们并不容易能够先筛出素数表。

即使空间允许。时间也不允许。

而这时。我们可以考虑去构造回文串。回文串的数量比素数的数量小得多。然后我们再去判断构造出来的回文数是否是素数。

 

对于这个问题。已经包含了“避多就少”的转化思想。

于是我们同样地可以思考这样的一个问题。已知N. 求M

使得N*M为一个回文素数。

这个问题就不加以分析了。

回归正题。

 

然而我们并不满足于穷举0 1串的复杂度（实际上其复杂度还是相当高的）。

这里利用和式的同余定理:

a mod p = m1 , b mod p = m2  -> (a+b) mod p = (a mod p + b mod p) mod p = (m1+m2) mod p 

针对整除问题的优化。

根据长度对我们构造出来的串进行划分。

1     10,11   100,101,110,111 ...

容易发现一个问题。

长度长的串除了原串 (1 10 100...)以外。都是由原串和长度小的串构成的。

比如 111 是由 100 + 11.

       110 是由 100 + 10.

       101 是由 100 + 1.

由此。我们可以利用动态规划的思想。保留处理出的结果为后续使用。（这里的结果其实就是余数）。

同时你会发现一个问题。

假如N = 3.

1  mod 3 = 1. 10 mod 3 = 1.即1 和 10 对于3 来说是等价的。

那么同理。  101 110 对于3来说也是等价的。

我们是否可以避免101 110这样的运算的呢？

 

答案当然是可以的。

我们可以只保留余数信息。同时可以在这个余数信息里存最小的串元素。

比如 BigInt[1] = 1.

这样的话。我们就不会重复计算同余数的数了。

 

套用编程之美上面的伪码。

<代码>

代码上令BigInt[]  为向量数组。方便操作。

同时放入i 是为了防止更新在当前长度新产生的余数集。

就比如：N = 3 的例子

1%3 = 1 有余数集1。

10%3 = 1 。余数集1已经存在。那么更新1+1 = 2 的余数集。

(在这之前都没问题，看下面。)

100%3 = 1 。余数集1已经存在。那么我们对余数集1 2 进行更新操作。 1+1=2 已经存在。 1+2 = 3 更新出3的集

（这是正常的操作）。

假如没有放入i。

就会变成

100%3 = 1。 余数1存在略过。1+1 = 2 存在略过。1+3 = 3 更新出3。之后又 1+3 = 4 更新出4 。 1+4 = 5 更新出 5 。