《最多约数问题》由会员分享，可在线阅读，更多相关《最多约数问题（2页珍藏版）》请在装配图网上搜索。
1、最多约数问题首先，有 必要明 确一下 如何求一 个数的因 子数 。若一 个数 N 满足N二PNi XPN2 XPN3 .xPNm，其中P, P，P是N的m个质因子。则N的约 123m12m数个数为（N + 1）（N + 1）（N + 1）.（N +1）。这一公式可以通过乘法原理来证123m明。有了求因子数的公式后，最容易想到的算法就是，枚举区间内的每个整数，统 计它们的约数个数。这个算法很容易实现，但是时间复杂度却相当高。因为区间 中整数的范围是11000000000 ,整个枚举一遍并计算因子数的代价约为 109x（ 105= 1013.（509X（109）0.5=1013.5）。这个规模是无
2、法忍受的。所以， 我们需要尽量优化时间。分析一下枚举的过程就会发现，如果我们分别枚举两个数n和p * n （p为一相 对较大的质数），那么我们将重复计算两次n的因子数。其实，如果枚举顺序得 当的话，完全可以在n的基础上去计算p * n，而如果能在n的基础上计算p * n， 就相当于计算p *n的因子数只用了 O（1）的时间。这是一个比较形象的例子，类 似的（可能相对更复杂一些）重复计算在枚举过程中应该是普遍存在的。这就是 枚举效率低的根本所在。为了解决这一重复，我们可以选取另一种搜索顺序 枚举质因子。这样的搜索顺序可以避免前面所说了类似n和p *n的重复计算。定义number为当前搜索到的数。
3、初始时，令number = 1，然后从最小的质数2 开始枚举，枚举因子中包含0个2个、个、k个 的情况直至 n u m b eX r2k 大 于 区 间 的 上 限 （max） 。 对 于 每 个 “ 2 k 的 情 况 ” ， 令 number = number *2k，在这个基础上，再枚举因子3的情况。然后在3的基础上 枚举因子5的情况，然后是7的情况整个过程是一个深度搜索的过程，搜索 的过程中，利用前面提到的求因子数的公式可以算出当前的number的因子数供 下一层枚举继承。当number大于等于区间下限（min）时，我们就找到了一个区间 内的数（枚举的过程已保证number不超过上界）
4、。所有枚举得到的区间内的数中， 因子数的最大值就是我们要求的目标。这样的枚举完全去除了重复计算，但是这还是不够的，因为光11000000000 内的数每枚举一遍就有 109 个单位的操作。所以，我们还需要找到一些剪枝的方 法，进一步优化时间。我们看到，如果当前搜索状态为(from, number, total)，其中，from是指当前 枚举到的质因子(按从小到大枚举)，total是指number中包含的因子数。那么剩 下的因子数最多为q = los 上亠，这些因子组成的因子个数最大为2q。因此，fromnumber当前所能取到的(理想情况)最大约数个数就是total。如果这个数仍然无法 超过当
5、前最优解，则这一分支不可能产生最优解，可以剪去。此外，如果(min -1)/ number = jnax / number ，则表示以当前状态搜索下去， 结果肯定不在区间内了，就无法产生合法解，也可剪去。不过，这一剪枝作用不 是很大，因为即使不剪，再搜索一层也就退出了。以上两个剪枝，前一个是最优化剪枝，后一个是合法性剪枝。相比较而言，前 一个剪枝的作用要大得多。下面我们用平摊分析的方法来讨论一下搜索的复杂度。由于枚举的过程中没有 重复计算，每枚举一个质因子，都可以得到一个不同的number (number max )， 所以可以将每一个单位的枚举质因子的代价与一个不超过max的number对应， 并且还可在两者之间建立双射。不同的number最多只有max个，所以枚举的总 代价不超过0 (max), max 109。加上了剪枝以后，计算总代价就远远小于0 (max) 了。从运行效果来看，即便 是最大数据，也可以很快出解。从本题的解决过程中可以看到，最关键的有两步：(1)采用合理的搜索顺序，避免重复计算；( 2)利用最优化剪枝和合法性剪枝，剪去一些不可能产生最优解或合法解的 分支。这两种优化的方法在搜索中的地位是极其重要的，当然可能在本题中的重要性 体现得格外突出。
最多约数问题
